정렬

• 정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것(오름차순, 내림차순 등)

1. 선택 정렬
2. 삽입정렬
3. 퀵 정렬
4. 계수 정렬

1. 선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 가장 앞에 있는 데이터와 바꾸는 것을 반복

✅예시

1. list=[5,3,8,1,2,7] =>1과 5데이터 변경
2. list=[1,3,8,5,2,7] =>2와 3데이터 변경
3. list=[1,2,8,5,3,7] => 3과 8데이터 변경
4. list=[1,2,3,5,8,7] => 7과 8데이터 변경
5. list=[1,2,3,5,7,8] => 정렬 완료

✅선택정렬 코드(python)

array=[5,3,8,1,2,7]

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]

print(array)

✅시간 복잡도

N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함
전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2
=>(N^2 + N - 2) / 2 이므로
=> O(N^2)

출처 : https://www.youtube.com/watch?v=jpyslMwprao&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=21

2. 삽입 정렬

• 처리되지 않은 데이터를 하나식 골라 적절한 위치에 삽입
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적임

✅예시 (맨 처음 데이터를 정렬된 것으로 가정)

1. list=[5,3,8,1,2,7] => 3을 삽입
2. list=[3,5,8,1,2,7] => 8은 이미 제자리
3. list=[3,5,8,1,2,7] => 1을 삽입
4. list=[1,3,5,8,2,7] => 2를 삽입
5. list=[1,2,3,5,8,7] => 7을 삽입
6. list=[1,2,3,5,7,8] => 정렬 완료

✅삽입정렬 코드(python)

array=[5,3,8,1,2,7]

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]
        else:
            break
print(array)

✅시간 복잡도

• O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용

• 만약 리스트의 데이터가 거의 정렬된 상태라면 매우 빠르게 동작하며, 이때 시간복잡도는 최선의 경우(이미 정렬된 경우) => O(N)

출처 : https://www.youtube.com/watch?v=DRkL5EBZ7KY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=22

3. 퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(pivot)로 설정
  

✅예시

• pivot을 기준으로 왼쪽에서부터는 pivot보다 큰 데이터를 선택하고, 오른쪽에서부터는 pivot보다 작은 데이터를 선택

-왼쪽부터 순서대로 탐색해 큰 값인 7과, 오른쪽부터 순서대로 탐색해 작은 값인 4를 바꿈

-다시 똑같은 방식으로 9와 2의 데이터를 바꿈

-반복하다가 엇갈리게 되는 순간 작은 값과 pivot의 위치를 바꿈

-pivot을 기준으로 왼쪽 부분과 오른쪽 부분을 나눠서 다시 반복

✅퀵 정렬 코드(python)_일반적인 코드

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

def quick_sort(array, start, end):
    if start >= end:  #array에 원소가 1개인 경우
        return
    pivot = start
    left = start+1
    right = end
    while(left <= right):
        while(left <= end and array[left] <= array[pivot]):
            #pivot보다 작은 큰 데이터 찾을 때까지 반복
            left += 1
        while(right > start and array[right] >= array[pivot]):
            # pivot보다 작은 작은 데이터 찾을 때까지 반복
            right -= 1
        if(left > right):   #엇갈리면 작은 데이터와 pivot 바꿈
            array[right], array[pivot] = array[pivot], array[right]
        else:   #아니면 큰 수와 작은 수 바꿈
            array[right], array[left] = array[left], array[right]
    #pivot을 기준으로 나눠진 왼쪽, 오른쪽에서 다시 정렬
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array) - 1)
print(array)

✅퀵 정렬 코드(python)_파이썬 장점 이용

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]     #pivot보다 작은 값
    right_side = [x for x in tail if x > pivot]     #pivot보다 큰 값

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

✅시간 복잡도

• 너비 x 높이 = N x logN = NlogN
  => O(NlogN)
• 하지만 이미 정렬된 배열에서는 최악의 경우
  => O(N^2)

출처 : https://www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=23

4. 계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

✅예시
가장 큰 수까지 빈 리스트를 만들고 해당 수가 나올때마다 count list의 해당 수 증가시킴

완료된 후에는 해당 수를 count list만큼 출력한다.

✅계수 정렬 코드(python)

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

count=[0] * (max(array)+1)  #빈 리스트 생성

for i in range(len(array)):
    count[array[i]] += 1    #해당 수의 인덱스에 1더하기

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

✅시간 복잡도
데이터이 개수가 N, 데이터(양수) 중 최대값이 K일 때, 최악의 경우에도
=>O(N+K)

출처 : https://www.youtube.com/watch?v=65Ui3RNibRA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=24