[알고리즘] 정렬 with 버블 , 삽입, 선택, 퀵, 병합 정렬

정렬이란

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

---

정렬 종류	버블 정렬	삽입 정렬	선택 정렬	퀵 정렬	병합 정렬
평균 시간복잡도
최악의 시간복잡도
최선의 시간복잡도	O(n)	O(n)
Runtime (60,000개 입력시) 단위 : sec	22.894	7.438	10.842	0.014	0.026

---

버블 정렬 (bubble sort) 란?

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
• 서로 비교해서 큰 값을 뒤로 보내는 것이다. (오름차순으로)
• 핵심
  • SWAP 방식

2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 버블정렬

[자바] 정렬 알고리즘 - 버블정렬

def bubblesort(data):
    for i in range(len(data) - 1):
        for index in range(len(data) - i - 1):
            if data[index] > data[index + 1]:
                data[index], data[index + 1] = data[index + 1], data[index]
        


a = [5, 3, 8, 7, 2, 9, 1]
n = len(a)
for i in range(n - 1, 0, -1): 
    for j in range(i):  # [0, i)
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

# 정렬이 되는 것은 제일 뒤이기 때문에 range(n - 1, 0, -1)로써 맨 앞에서부터 계속 정렬을 시도하는 것으로 작성

---

삽입 정렬 (insertion sort) 란?

• 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
• 좌측은 이미 정렬이 되어있어 내가 선택한 값과 비교를 통해 알맞은 위치에 삽입을 한다는 것이다.

2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 삽입 정렬

[자바] 정렬 알고리즘 - 삽입 정렬

 

def insertion_sort(data):
    for i in range(len(data)-1):
        for j in range(i+1,0,-1):
            if data[j-1] >data[j]:
                data[j-1] , data[j] =data[j],data[j-1]
            else:
            	break
                
                
a = [5, 3, 8, 4, 7, 6, 1, 9, 2] 

def insertion_sort(a, n=len(a)):
    for i in range(1, n):  
        val = a[i]
        j = i -1
        while j >= 0 and a[j] > val:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = val
    return a

insertion_sort(a)

---

선택 정렬 (selection sort) 란?

• 밑과 같은 순서를 반복하며 정렬하는 알고리즘

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 선택정렬

[자바] 정렬 알고리즘 - 선택정렬

def selection_sort(data):
    for i in range(len(data)-1):
        min_index=i
        for j in range(i+1,len(data)):
            if data[min_index]>data[j]:
                min_index=j
        data[min_index],data[i]=data[i],data[min_index]


def selection_sort(a, n=len(a), show_steps=False, reverse=False):

    for i in range(n - 1):
        idx = i
        for j in range(i, n):
            if (not reverse) and (a[idx] > a[j]):
                idx = j  # find min index
            
            if reverse and (a[idx] < a[j]):
                idx = j  # find max index

        a[i], a[idx] = a[idx], a[i]

        if show_steps:
            print(f"{a[:i+1]}  {a[i+1:]}")
    return a

 

---

퀵 정렬 (quick sort) 이란?

• 정렬 알고리즘의 꽃
• Divide and Conquer로 분할 정복 알고리즘이다.
• 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함

Lomuto Partition 방식

- 분할 방법중 하나로 pivot의 위치를 tail인 끝점으로 지정하고 하는 것이다.

 

def partition(a, head, tail):
    pivot = a[tail]
    mid = head
    for i in range(head, tail):
        if pivot > a[i]:
            a[i], a[mid] = a[mid], a[i]
            mid += 1

    a[tail] = a[mid]
    a[mid] = pivot
    return mid

def quick_sort(a, head=0, tail=len(a)-1):
    if head >= tail:
        return 
    
    mid = partition(a, head, tail)
    quick_sort(a, head, mid-1)
    quick_sort(a, mid+1, tail)

 

 

Hoare Partition 방식

- 분할 방법중 하나로 pivot의 위치를 head인 처음(맨 왼쪽)으로 지정하고 하는 것이다.

def partition(a, head, tail):
    pivot = a[head]
    right = tail
    for i in range(tail,head,-1):
        if pivot < a[i]:
            a[i], a[right] = a[right], a[i]
            right -= 1

    a[head] = a[right]
    a[right] = pivot
    return right
    
def quick_sort(a, head=0, tail=len(a)-1):
    if head >= tail:
        return

    mid = partition(a, head, tail)  
    quick_sort(a, head, mid-1)
    quick_sort(a, mid+1, tail)
    
    
    
#또다른 partion에 해당하는 것
def partition(a, head, tail):
    pivot, i, j = a[head], head+1, tail

    while i <= j:
        while i <= tail and a[i] < pivot: i += 1        
        while j >= head and a[j] > pivot: j -= 1
        if i < j: a[i], a[j] = a[j], a[i]
    
    a[head] = a[j]
    a[j] = pivot
    return j

---

병합 정렬 (merge sort)

• 재귀용법을 활용한 정렬 알고리즘
• Divide and Conquer로 분할 정복 알고리즘이다.

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 병합 정렬

[자바] 정렬 알고리즘 - 병합 정렬

 

오름차순 

def merge_sort(a, head, tail):
    if head >= tail:  # 원소가 한개 이하가 됐을때
        return

    mid = (head + tail) // 2

    merge_sort(a, head, mid)
    merge_sort(a, mid+1, tail)
    merge(a, head, mid, tail)


def merge(a, head, mid, tail):
    i, j = head, mid+1
    tmp, t = [0 for _ in range(len(a))], head

    while (i <= mid) and (j <= tail):
        if a[i] < a[j]:
            tmp[t] = a[i]
            t ,i = t+1 ,i+1
        else:
            tmp[t] = a[j]
            t ,j = t+1 ,j+1

    while i <= mid:
        tmp[t] = a[i]
        t ,i = t+1 ,i+1

    while j <= tail:
        tmp[t] = a[j]
        t ,j = t+1 ,j+1
        
    a[head:tail+1] = tmp[head:tail+1]

 

내림차순

 

def merge(a, head, mid, tail):
    i, j = head, mid+1
    tmp, t = [0 for _ in range(len(a))], head

    while (i <= mid) and (j <= tail):
        if a[i] > a[j]:
            tmp[t] = a[i]
            t ,i = t+1 ,i+1
        else:
            tmp[t] = a[j]
            t ,j = t+1 ,j+1

    while (i <= mid):
        tmp[t] = a[i]
        t ,i = t+1 ,i+1

    while (j <= tail):
        tmp[t] = a[j]
        t ,j = t+1 ,j+1

    a[head:tail+1] = tmp[head:tail+1]