정렬 코드1(계수 정렬, 삽입 정렬, 선택 정렬)

계수 정렬 (count sort)

• 계수정렬은 데이터의 크기 범위가 제한되어 정수형태로 표현될 수 있을때 효과적으로 사용할 수 있다. (일반적으로 큰 데이터와 작은 데이터의 차이가 1,000,000이 넘지 않을때 사용한다.)
• 데이터의 개수가 N, 데이터 중 최대값이 K일때, 최악의 경우에도 O(n+k)의 수행시간을 보장하는 빠른 정렬법이다.
• 동작원리는 만약 최소0부터 최대1,000,000의 데이터가 주어지는 경우, '모든 범위를 담을 수 있는 리스트' - 즉 1,000,001개의 리스트를 선언하여 각 값을 담는것이다. 그래서 매우 큰 범위는 사용할 수 없다.

---

def count_sort(array):

    count = [0] * (max(array) + 1)

 

    for i in range(len(array)):

        count[array[i]] += 1         # (array[0] = 7) => count[7] += 1

 

    for i in range(len(count)):

        for _ in range(count[i]):     # count[1]가 만약 3이라면 1을 3번 반복하여

            print(i, end=' ')            # 1 1 1 이라는 출력을 한다.

---

삽입 정렬 (insertion sort)

• 평균적으로 O(n^2)의 시간복잡도를 가지지만 현재 데이터 리스트가 거의 정렬된 상태일때 최대 O(n)의 시간복잡도를 가진다.
• 즉, 주어진 데이터가 거의 정렬된 상태라면 퀵정렬보다 더 효율적이므로 데이터의 상태를 보고 사용하면 효과적이다.

---

def insertion_sort(array):

    for i in range(1, len(array)):    

        for j in range(i, 0, -1):

            if array[j] < array[j - 1]:

                array[j], array[j - 1] = array[j - 1], array[j]      # 만약 array[i]보다 array[i-1]이 크다면 두 인덱스 스왑

            else: break

    return(array)

---

선택 정렬 (selection sort)

• 직관적이지만 O(n^2)의 시간복잡도를 가져 매우 느리므로 사용할 일은 적다.
• 정렬의 기본 코드로 진행 방식을 이해하기 좋은 코드이다.

 

---

def selection_sort(array):

    for i in range(len(array)):

        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]

    return(array)