Chapter 6. 정렬

 

1. 선택정렬:

 

매번 가장 작은것을 선택해서 정렬 안된 부분의 가장 첫번째 위치에 자리시킨다.

                  tip) 파이썬의 스와이프는 매우 간단하다는 것을 이용하자

         

-시간 복잡도: O(n^2)

 

 

2. 삽입정렬:

 

이미 정렬된 리스트에 데이터 하나를 삽입 할때 적절한 위치에 삽입하면 되는 것을 착안한다는 식으로 구현하면 된다.

                    현재 가르키고 있는 인데스 앞부분은 이미 정렬되어 있다고 본다(실제로 정렬 되어 있을것이다.). 인덱스를 점차 증가 시키면서 

                    앞의 배열에 삽입하는 식으로 거의 정렬된  리스트에 효과적이다.

       

- 시간 복잡도 : O(n^2),   거의 정렬되어 잇을 경우 -> O(n)

 

 

3. 퀵정렬: 

 

재귀식으로 작동한다. 3가지 포인트만 기억하자

1. 피벗 정하기

2. 왼쪽 부분 오른쪽 부분 각 두 지점에서 출발하여 왼쪽 부분에서 시작했으면 피벗보다 큰값을 찾고 오른쪽 부분에서 시작했으면 피벗보다 작은값 찾기

3. 2번에서 찾은 값을 서로 스와이프 하면서 진행 하다가 서로 엇갈리면 '분할완료'

재귀식으로 피벗 왼쪽 부분을 퀵소트 하고 오른쪽 부분을 퀵소트 한다. 탈출 조건은 리스트 길이가 1 이하면 탈출

 

이는 파이썬으로 엄청 간단하게 구현 가능하다.

책에 있는 코드를 그대로 보이면

 

array = [5,7,0,9,3,1,6,2,4,8]

def quick_sort(array):
	if (len(array) <= 1):
    	return
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
 
 print(quick_sort(array))

                    

-시간 복잡도: O(nlogn)

 

 

4. 계수 정렬:

 

특정한 조건일 때만 사용할수 있지만 매우 빠르게 동작한다. 

만일 array의 숫자중 가장 큰 숫자가 n 이라면 인덱스 n을 참조할 수 있을만한 배열 크기를 만들어 준다(크기: n+1).

그 다음에 몇번 숫자가 나왔는지 카운트 해서 적어주면 된다. 그다은 카운터를 저장한 배열을 보고 순서대로 숫자를 입력하면 그게 정렬되어 있는 것이다. 

매우 간단하고 빠르게 동작하지만 만일 정렬하고 싶은 숫자가 0과 999999 단 두개를 정렬 하고자 한다 해도 카운트를 위해서 만들어야할 배열의 길이는 1000000일 것이다. 즉 공간 복잡도가 매우 높다. 하지만 동일한 값을 가지는 데이터가 여러 개 등장 할 때에는 효과적이다.

 

5. 파이썬 정렬 라이브러리:

 

1. ex) result = sorted(array)

     -별도의 정렬된 리스트 객체가 반환된다

     -집합 자료형이나 딕셔너리 자료형을 입력 받아도 결과는 리스트 자료형으로 반환된다.

 

2. ex) array.sort()

      -별도의  정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

 

3. sort() 나 sorted()에서 key 매개변수로 무엇을 기준으로 정렬할 것인지를 정 할 수 있다.

      -  따로 함수를 설정 할 수 있고, 또는 람다식을 이용한다. 개인적으로 알고리즘에선 람다식이 되게 편하다.

 

6. 코딩테스트의 정렬 라이브러리 문제 유형

 

1) 정렬 라이브러리로 풀 수 있는 문제

 

2) 정렬 알고리즘의 원리에 대해서 물어보는 문제

 

3) 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서              

                                                기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있는 문제