정렬

<이것이 취업을 위한 코딩테스트다>를 공부하며 정리한 내용입니다.

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬

• 매번 가장 작은 것을 선택한다 → 선택 정렬 알고리즘
• 가장 작은 것을 선택해서 앞으로 보내는 과정의 연속.

예제

N(데이터의 개수)=10인 경우.

1. 초기 단계 : 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 그리고 가장 앞에 있는 7과 자리를 바꿔준다.

   7 5 9 0 3 1 6 2 4 8

2. 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 ‘1’을 선택해서 처리하지 않은 데이터 중 가장 앞에 있는 5와 바꾼다.

   0 5 9 7 3 1 6 2 4 8

3. 2와 9 바꾸기

   0 1 9 7 3 5 6 2 4 8

4. 0 1 2 7 3 5 6 9 4 8

5. 0 1 2 3 7 5 6 9 4 8

6. 0 1 2 3 4 5 6 9 7 8

7. 0 1 2 3 4 5 6 9 7 8

8. 0 1 2 3 4 5 6 9 7 8

9. 0 1 2 3 4 5 6 7 9 8

10. 0 1 2 3 4 5 6 7 8 9

⇒ 총 9번(N-1번)만 반복하면 정렬이 완료됨!

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

for i in range(len(array)-1):
    min_index=i #가장 작은 원소의 인덱스
    for j in range(i+1,len(array)):
        if array[min_index]>array[j]:
            min_index=j

    array[i], array[min_index]= array[min_index],array[i]

print(array)

시간 복잡도

• 이중 포문 → O(N^2)
• 다른 정렬 알고리즘과 비교했을 때 효율적인 편이 아님.
• 구현 난이도 : 하
• 다만 이렇게 리스트에서 최솟값 찾는 문제에서 비슷하게 코드를 사용하니 잘 봐주자!

삽입 정렬

• 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하기.
• 필요할 때만 위치를 변경해줌 → 효율적. (특히, 데이터가 거의 정렬되어 있을 때)
• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정. 실제로 정렬되어 있긴 함.
• 두 번째 데이터부터 위치 변경 목표가 됨. 첫 번째 데이터는 이미 정렬되어 있다고 생각해서 그것의 오른쪽 혹은 왼쪽에 놓을지 결정하면 됨.
• 목표 데이터는 한칸씩 왼쪽으로 이동하다가 자신보다 작은 수를 만났을 때 그 앞에 멈추면 됨.

예제

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

1. <5> 5 7 9 0 3 1 6 2 4 8
2. <9> 5 7 9 0 3 1 6 2 4 8
3. <0> 0 5 7 9 3 1 6 2 4 8
4. <3> 0 3 5 7 9 1 6 2 4 8
5. <1> 0 1 3 5 7 9 6 2 4 8
6. <6> 0 1 3 5 6 7 9 2 4 8
7. <2> 0 1 2 3 5 6 7 9 4 8
8. <4> 0 1 2 3 4 5 6 7 9 8
9. <8> 0 1 2 3 4 5 6 7 8 9

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

for i in range(1,len(array)): 
    for j in range(i,0,-1): #i(타깃)에서 1까지 거꾸로 내려가면서 앞에꺼랑 비교함.
        if array[j]<array[j-1]: #내가 앞에꺼보다 작으면
            array[j], array[j-1]=array[j-1],array[j] #나랑 자리 바꾸자
        else: #앞에꺼가 더 크면
            break #거기가 니 자리

print(array)

시간 복잡도

• 이중 반복문 → O(N^2)
• 만약, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하니 이를 사용하자!! 퀵 정렬보다도 빨라짐.
• 최선의 경우(다 정렬되어있다면) → O(N)

퀵 정렬

• 가장 많이 사용되는 알고리즘
• pivot 이라는 개념이 등장‼
• 호어 분할(Hoare Partition) 방식 : 리스트에서 첫 번째 데이터를 피벗으로 정한다.
• 피봇보다 작은 수를 피봇 왼쪽으로, 큰 수를 피봇 오른쪽으로 보내려는 알고리즘.
• 우선은 왼쪽부터 피봇보다 큰 수를 찾고, 오른쪽에서부터는 작은 수를 찾아 자리를 바꿔준다.
• 그리고 큰 수가 작은 수보다 뒤에 있으면 잘 정렬된 거니 그 두 수 사이에 피봇을 넣어준다.
• 재귀 함수를 이용한 코드!

예제

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

(직접 필기로 계산해보는 것을 추천!!)

1. 퀵 정렬 소스코드 (정석 ver)

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

def quick_sort(array,start,end):
    if start>=end: #원소가 1개밖에 없는 경우
        return

    pivot=start
    left=start+1
    right=end

    while left<=right: #같은 피봇일 동안 엇갈리지 않는이상 반복실행

        #왼쪽에서부터 피봇보다 큰 값 찾기 
        while left<=end and array[left]<=array[pivot]: 
            left+=1

        #오른쪽에서부터 피봇보다 작은 값 찾기
        while right>start and array[right]>=array[pivot]:
            right-=1

        #만약 엇갈렸다면 작은 값과 피봇을 바꾸기
        if left>right:
            array[right], array[pivot]=array[pivot], array[right]

        else: #아니라면 작은값과 큰값 자리 바꾸기
            array[left],array[right]=array[right], array[left]

    #피봇 왼쪽과 오른쪽 분할하여 똑같이 실행해주
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array,0,len(array)-1)
print(array)

1. 파이썬 리스트 이용한 코드 (심플 ver) : 코드는 짧지만 시간 면에서는 좀 비효율적.

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

def quick_sort(array):
    
    #리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <=1:
        return array

    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)
• 최악의 경우😥 (이미 데이터가 정렬되어 있는 경우) : O(N^2)
• 이미 데이터가 정렬되어 있는 경우 다른 정렬 알고리즘에 비해 효율적이지 않다..

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠름.
• 가장 큰 데이터와 가장 작은 데이터의 차이가 별로 크지 않을 때 사용
• 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 함. (min~max의 모든 정수)
• min-max의 모든 정수를 담은 하나의 리스트. 요소 모두 0으로 초기화해서 생성.
• 데이터에서 하나씩 정수 빼보면서 각 인덱스의 값+1 해주기.
• 카운트된 만큼 앞에서부터 차례대로 출력해주면 됨.

예제

데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 (0~9)

1. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	1	0	0

1. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	0

1. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	1	0	1	0	1

(생략)

1. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
2	2	1	1	1	2	1	1	1	2

1. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

0	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

⇒ 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

#모든 원소의 값이 0보다 크거나 같다고 가정
array=[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count=[0]*(max(array)+1)

for i in array:
    count[i]+=1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

⇒ 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

시간 복잡도

• O(N+K) : 데이터의 개수 N, 데이터 중 최대값의 크기 K
• 동일한 값을 가지는 데이터가 여러 개 등장하고, 데이터의 범위가 한정되어 있을 때 적합.

코딩 테스트에서의 정렬 알고리즘

1. 정렬 라이브러리로 풀 수 있는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
3. 더 빠른 정렬이 필요한 문제 → 계수 정렬이나 다른 알고리즘 필요…