[Python] 정렬 알고리즘 - 선택, 삽입, 퀵, 계수

1. 선택 정렬 Selection Sort

: 가장 작은 데이터를 선택하여 맨 앞으로 보내고 그 다음 작은 데이터를 선택해서 두번째 데이터와 바꾸는 과정
  시간복잡도 : O(n^2) 많이 느리다

 

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

for i in range(len(a)):
    min_index = i #비교할 인덱스 0번부터 시작

    for j in range(i+1,len(a)): #그 다음부터 비교 시작
        if a[min_index]>a[j]:
            min_index = j
    
    a[i],a[min_index] = a[min_index],a[i]

print(a)

 

2. 삽입 정렬 Insertion Sort

 

: 맨 첫번째 원소를 기준으로 두번째 원소부터 비교한다. 차례대로 앞에 원소들과 비교하는데 앞에 원소보다 작으면

  자리를 바꾸고 크면 멈춘다.

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

 

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

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

    for j in range(i,0,-1): #앞으로 가면서 비교
        if a[j]<a[j-1]:
            a[j],a[j-1] = a[j-1],a[j]
        
        else :
            break

print(a)

 

3. 퀵 정렬 Quick Sort

: 기준 pivot을 정해 pivot보다 작으면 왼쪽 크면 오른쪽으로 분류. 

  시간복잡도 O(n log n)

def quick_sort(arr):

    if len(arr)<=1:
        return arr

    pivot = arr[0]
    tail = arr[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(a))

 

4. 계수 정렬 (Count Sort)

 

: count에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다.

  count 인덱스가 a에 있는 원소라고 보고, a값이 나오는 횟수 라고 보면 된다.

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

count = [0]*(len(a)+1)

for i in range(len(a)):
    count[a[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