[Python] 정렬

선택 정렬

3-1. 정렬(선택)

- 가장 작은 데이터를 선택하여 맨 앞으로 보내 순서대로 정렬하는 방식
    ~ 최소값을 찾아서 맨 앞으로 교체한다.

- 맨 앞부터 작은 데이터를 채워넣음.

- 이미 정렬되어 있어도 상관 없이 작은 값을 찾아서 수행하기 때문에 성능이 떨어짐.
    ~ 맨앞은 이미 정렬된 상태이므로, 맨앞은 제외하고 나머지 부분에서 다시 최소값을 찾아서 앞으로 교체한다.(반복)

- 반복문을 통해 모든 인덱스에 접근이 필요함.

- 시간 복잡도 O(n²)

선택 정렬

list = [64, 25, 12, 22, 11]

for i in range(0, len(list)) :

    min_idx = i
    
    for j in range(i+1, len(list)):
        
        if list[min_idx] > list[j] :
            
            min_idx = j

    list[i], list[min_idx] = list[min_idx], list[i]


for i in range(0, len(list)) :
    print("%d" %list[i], end = " ")

---

버블 정렬

3-2. 정렬(버블)

- 뒤에서부터 앞으로 정렬하는 구조

- 맨 뒤에 가장 높은 값을 보내고 그 앞에 두 번째로 큰 값을 보냄.

- 배열 내에서 앞과 뒤를 서로 비교하여 자리를 바꾸는 작업을 반복 수행함.

- 선택배열과 반대로 큰 값을 뒤로 보내면서 앞 뒤를 비교하여 위치를 변경하는 모습을 물방울이 이동하는 것에 비유함.

- 시간복잡도 O(n²)

list = [10, 9, 2, 4, 7]

for i in range(0, len(list)) :

    for j in range(0, len(list)-i-1) : # -i : 맨 뒤로 한 번 정렬했으면 다시 볼 필요 x

        if list[j] > list[j+1] :
            
            list[j], list[j+1] = list[j+1], list[j]


for i in range(0, len(list)) :
    print("%d" %list[i], end = " ")

---

삽입 정렬

3-3. 정렬(삽입)

- 배열은 정렬된 부분과 정렬되지 않은 부분으로 나뉨.

- 정렬 부분의 마지막 값과 비정렬된 맨 앞의 값과 비교한다.
 
1. 정렬 부분의 값이 비정렬된 값보다 작으면 비정렬된 값을 맨 뒤에 붙인다.
2. 정렬 부분의 마지막 값이 비정렬된 맨 앞값보다 크면 교체한다.
    2-1. 그 앞 값과 반복 비교하고 교체한다.

- 시간복잡도 O(n²)

삽입 정렬

list = [12, 11, 13, 5, 6]

for i in range(1, len(list)):
    j = i
    # 이전의 수 보다 타겟이 작아지는 것이 한 번 이라도 나타날 때까지 루프
    while j > 0 and list[j - 1] > list[j]:
        list[j - 1], list[j] = list[j], list[j - 1]
        j -= 1
        
for i in range(0, len(list)) :
    print("%d" %list[i], end = " ")

 

list = [12, 11, 13, 5, 6]

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

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

        if list[j-1] > list[j] :
            list[j-1], list[j] = list[j], list[j-1]


for i in range(0, len(list)) :
    print("%d" %list[i], end = " ")

---

퀵 정렬

4. 정렬(퀵)★★★

- 분할정복(Devide & Conquer)★★★ 기법과 재귀호출을 이용함.
    ~ 분할정복은 문제를 작은 2개로 분리하고 각각 해결한 뒤 결과를 모아서 원래의 문제를 해결하는 방식
    ~ 비균등분할(머지소트는 균등분할) #반반 나누는 것x 개수는 상관 없다. (4/4 아니라 3/5 가능)

- pivot이라는 변수를 사용함.
    ~ 임의의 기준값 변수(첫 요소 선택, 마지막 요소 선택, 임의 선택, 중앙값 선택)
    ~ pivot 변수를 기준으로 분할함.(이때 pivot 변수 자체는 이미 정렬된 것)

- pivot 변수를 기준으로 더 작은 값과 더 큰 값으로 반복적으로 분할하여 정렬함.

- 파이썬 내장함수인 sort()도 퀵 정렬을 기본으로 함.

- pivot값에 따라 성능이 크게 달라짐.

- 주로 pivot값은 중간값으로 설정함.

- 시간 복잡도: 이상적일 경우 O(n log n), 최악일 경우 O(n²)
    ~평균적으로 빠른 수행 속도

퀵 정렬

def partition(list, low, high) :

    #pivot 설정(맨 뒷값)
    pivot = list[high]
    i = low - 1

    for j in range(low, high) :
        if (list[j] <=pivot) : #i 1 증가, i값 j값 교체
            i += 1
            list[i], list[j] = list[j], list[i]

    list[i+1], list[high] = list[high], list[i+1]

    return i+1

def quick_sort(list, low, high) :
    if (low < high) :
        pivot = partition(list, low, high)

        quick_sort(list, low, pivot-1) #왼쪽
        quick_sort(list, pivot+1, high) #오른쪽
        
list = [10, 60, 30, 20, 50, 70, 40]
quick_sort(list, 0, 6)

print(list)

 

def quick_sort(list) :

    if (len(list) <= 1) :
        return list

    pivot = list[len(list)-1] #pivot 값 지정

    left_list, middle_list, right_list = [], [], []

    for i in list :
        if i < pivot :
            left_list.append(i)
        elif i > pivot :
            right_list.append(i)
        else :
            middle_list.append(i)

    return quick_sort(left_list) + middle_list + quick_sort(right_list)
            
list = [10, 60, 30, 20, 50, 70, 40]
quick_list = quick_sort(list)

print(quick_list)

---

머지 정렬

5. 정렬(머지)

- 퀵소트와 마찬가지로 분할정복 기법과 재귀호출을 이용함.

- 마지막의 크기가 0 또는 1이 될 때까지 절반씩 분할하여 정렬한다.

- 절반씩 균등분할

- 시간복잡도는 O(n log n)

머지 정렬

def merge_sort(list) :
    if len(list) <= 1 :
        return list
    
    else :
        #분할
        mid = len(list) // 2
        left = list[ : mid]
        right = list[mid : ]

        merge_sort(left)
        merge_sort(right)

        #병합    
        i = j = k = 0        
        while i < len(left) and j < len(right): #1개씩 있는 것 병합
            if left[i] < right[j]:
                
                list[k] = left[i]
                i += 1
            else:
                list[k] = right[j]
                j += 1
            k += 1
                
        while i < len(left):
            list[k] = left[i]
            i += 1
            k += 1
            
        while j < len(right):
             list[k] = right[j]
             j += 1
             k += 1

list = [10, 60, 30, 20, 50, 70, 40]
merge_sort(list)
print(list)