설명
버블 소트란
서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않을 경우 자리를 교환하며 정렬하는 알고리즘
이다.이름의 유래
정렬 과정에서 원소의 이동이 거품이 수면 위로 올라오는 듯한 모습을 보이기 때문
과정
1회전 : n-1과 n번째 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
1회전을 수행하면 가장 큰 원소가 맨 뒤[-1]로 이동하게 된다.2회전 : 1회전에서 가장 큰 원소가 맨 뒤로 이동하므로, 원소 정렬 과정에서 맨 끝에 있는 원소를 제외한다.
2회전을 수행하면 그다음 큰 원소가 맨 뒤에서 두번째 위치[-2]로 이동한다.
구현
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 1
print(i," ",1,n-i,arr)
for j in range(1, n-i): # 2
if arr[j-1] > arr[j]: # 3
arr[j-1], arr[j] = arr[j], arr[j-1]
print(arr)
bubble_sort([1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7])
"""
0 1 14 [1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1 1 13 [1, 0, 4, 6, 3, 2, 5, 7, 3, 5, 8, 7, 7, 8]
2 1 12 [0, 1, 4, 3, 2, 5, 6, 3, 5, 7, 7, 7, 8, 8]
3 1 11 [0, 1, 3, 2, 4, 5, 3, 5, 6, 7, 7, 7, 8, 8]
4 1 10 [0, 1, 2, 3, 4, 3, 5, 5, 6, 7, 7, 7, 8, 8]
5 1 9 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
6 1 8 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
7 1 7 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
8 1 6 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
9 1 5 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
10 1 4 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
11 1 3 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
12 1 2 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
13 1 1 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""
제외될 원소의 개수를 의미한다.
i회전이 끝나면 배열의 n-i 인덱스에 i번째 큰 원소가 위치한다.j는 비교할 원소의 인덱스를 의미한다.
j-1 : 이전 원소, j : 현재 원소두 원소의 크기 비교를 한다.
이전 원소가 현재 원소보다 크면 두 자리를 교환한다.
시간복잡도
n-1
n-2
n-3
...
2
1
=> n(n-1)/2 => O(n^2)정렬되있지 않은 배열 속 원소들을 비교하기 때문에
최선, 최악, 평균의 경우 모두 시간복잡도가 O(n^2) 이다.
공간복잡도
교환을 통해 정렬이 수행된다. n개의 원소에 대해 n개의 메모리를 사용한다.
=> O(n)
장점
구현이 간단하고, 소스코드가 직관적이다.
정렬을 하는 과정에서 주어진 배열 이외의 다른 메모리 공간을 요하지 않는다
안정 정렬이다.
단점
시간복잡도가 최악,최선,평균 모두 O(N^2)
정렬되어있지 않을 원소에 대한 교환 연산이 많이 일어난다.
설명
해당 순서에 원소를 넣을 위치는 이미 정해져 있고,
어떤 원소를 넣을지 선택하는 알고리즘이다.
- 해당 자리를 선택하고
- 그 선택한 자리에 올 값을 찾는 것
과정
[9,1,6,8,4,3,2,0]
1. 앞에서 부터 데이터를 하나 선택한다. ->9
2. 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾는다. -> min(arr[1:]) == 0
3. 찾은 최소값과 1번에서 선택한 원소의 자리를 바꾼다.
-> 9와 0의 자리를 바꾼다.
구현
def selection_sort(arr):
n = len(arr)
print(f"{arr=}")
for i in range(n-1):
idx = i
for j in range(i+1, n):
if arr[idx] > arr[j]:
idx = j
arr[i], arr[idx] = arr[idx], arr[i]
print(f"{i}: {i+1},{n} {arr}")
print(arr)
"""
arr=[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
0: 1,14 [0, 4, 1, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1: 2,14 [0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
2: 3,14 [0, 1, 2, 6, 8, 3, 4, 5, 7, 3, 5, 8, 7, 7]
3: 4,14 [0, 1, 2, 3, 8, 6, 4, 5, 7, 3, 5, 8, 7, 7]
4: 5,14 [0, 1, 2, 3, 3, 6, 4, 5, 7, 8, 5, 8, 7, 7]
5: 6,14 [0, 1, 2, 3, 3, 4, 6, 5, 7, 8, 5, 8, 7, 7]
6: 7,14 [0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 5, 8, 7, 7]
7: 8,14 [0, 1, 2, 3, 3, 4, 5, 5, 7, 8, 6, 8, 7, 7]
8: 9,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 8, 7, 8, 7, 7]
9: 10,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7]
10: 11,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 7]
11: 12,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
12: 13,14 [0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""
시간 복잡도
n-1 + n-2 + ... + 2 + 1 = n(n-1)/2
=> O(N^2)
최선, 최악, 평균의 경우 모두 동일
공간 복잡도
n개의 원소를 교환을 통해 정렬이 수행된다
=> O(N)
장점
알고리즘이 단순하다
버블 소트보다 교환하는 횟수는 적다
제자리 정렬이다 = 배열속에서 교환하는 방식 = 다른 메모리 공간이 필요하지 않는다.
단점
시간복잡도가 O(N^2)으로 비효율적
불안정 정렬이다.
설명
배열의 모든 요소를 앞에서부터 차례대로
이미 정렬된 배열 부분과 비교하여
자신의 위치를 찾아 삽입하여 정렬을 완성한다.다시말해
2번째 원소부터 시작하여
현재 i번째일 경우, arr[0:i-1]의 원소들과 비교하여
삽입할 위치를 지정한뒤
원소를 뒤로 옮기고 지정된 자리에 자료를 삽입한다.최선의 경우 O(N)이라는 빠른 효율성을 가진다.
과정
- 정렬은 2번째 인덱스부터 시작(선택)한다
(맨 처음 정렬할 경우에만. 왜냐하면 첫번째 리스트는 1번째 인덱스의 원소 하나로만 이루어진 정렬된 상태로 보기 때문이다.)
그리고 선택한 원소를 key 변수에 저장한다.- key 변수와 key변수보다 앞에 있는 원소들과 크기 비교 후 올바른 위치에 key 변수를 삽입한다.
1번
으로 돌아가 그 다음 인덱스를 key 변수에 저장한다.
구현
def insertion_sort(arr):
n = len(arr)
print(arr)
for i in range(1, n):
key = arr[i]
print(f"{i}: {key=}")
prev = i - 1
while prev >= 0 and arr[prev] > key:
arr[prev + 1] = arr[prev]
prev -= 1
print(arr)
arr[prev + 1] = key
print(f"{arr} !!")
print(arr)
"""
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
1: key=4
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
2: key=0
[1, 4, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[1, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
3: key=6
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
4: key=8
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] !!
5: key=3
[0, 1, 4, 6, 8, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 4, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 6, 8, 2, 5, 7, 3, 5, 8, 7, 7] !!
6: key=2
[0, 1, 3, 4, 6, 8, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 6, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 4, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 3, 3, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 6, 8, 5, 7, 3, 5, 8, 7, 7] !!
7: key=5
[0, 1, 2, 3, 4, 6, 8, 8, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 6, 6, 8, 7, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 3, 5, 8, 7, 7] !!
8: key=7
[0, 1, 2, 3, 4, 5, 6, 8, 8, 3, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 3, 5, 8, 7, 7] !!
9: key=3
[0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 5, 8, 7, 7] !!
10: key=5
[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7] !!
11: key=8
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 7, 7] !!
12: key=7
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 7]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 7] !!
13: key=7
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8] !!
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8]
"""
- 배열의 첫번째 원소 앞부분에는 원소가 없기 때문에 두번째 원소부터 탐색을 시작한다.
key 변수에 임시로 해당 인덱스의 값을 저장하고, prev 변수에는 해당 위치 바로 이전 위치를 저장한다.- 이전 위치를 가리키는 변수 prev가 음수가 되지 않고, 1번에서 선택한 원소보다 클 경우에만 서로의 값을 교환해주고, prev 변수를 더 이전의 위치를 가리키도록 -1 한다.
- 2번의 반복문이 끝나면
prev 변수에는 key값보다 작은 값들중 가장 큰 값의 위치가 담겨 있다.
따라서 prev 위치 바로 뒤에 key 변수에 담긴 값을 넣어준다.
시간복잡도
(n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2
=> O(N^2)
하지만 입력된 배열이 정렬된 경우
비교 연산을 1번씩만 하게된다
=> 최선의 경우 O(N), 최악,평균이 경우 O(N^2)
공간복잡도
n크기의 배열에서 교환이 n번 수행된다 => O(N)
장점
원소가 이미 정렬된 경우, 매우 효율적
제자리 정렬이다 = 배열안에서 교환하므로 다른 메모리 공간을 필요로하지 않는다.
안정 정렬이다.
선택정렬, 버블 정렬보다 상대적으로 빠르다
단점
최악,평균의 경우 시간복잡도가 O(N^2)이다
배열의 길이가 길어질 수록 비효율적이다.
선택정렬과 비교
유사점
k번째 반복 이후, 첫번째 k요소가 정렬된 순서로 온다차이점
선택정렬 : k+1번째 요소를 찾기 위해 나머지 모든 요소를 탐색
삽입정렬 : k+1번째 요소를 배치하는데 필요한 요소만 탐색 (훨씬 효율적)
설명
분할 정복 (divide and conquer) 방법
을 통해 배열을 정렬한다.분할정렬이란
문제를 작은 2개의 문제로 분리하여 각각 해결한 뒤,
결과를 모아서 원래의 문제를 해결하는 전략불안정 정렬에 속한다.
다른 원소와의 비교만으로 정렬을 수행할 수 있다 => 비교정렬
merge sort와 달리 배열을 비균등하게 분할한다.
과정
- 배열 가운데에서 하나의 원소를 고른다. 고른 원소를 피벗(pivot)이라고 한다.
- 피벗앞에는 피벗보다 작은 원소들이 오고
피벗 뒤에는 피벗보다 큰 우너소들이 오도록
피벗을 기준으로 배열을 둘로 나눈다.
이렇게 배열을 둘로 나누는 것을 분할(divide)라고 한다.- 분할된 두개의 작은 배열에 대해 재귀적으로 1,2번 과정을 반복한다.
구현
def quick_sort(arr, left, right):
if left >= right:
return
print(f"{left=} {right=} \n{arr}")
pivot = partition(arr, left, right)
quick_sort(arr, left, pivot - 1)
quick_sort(arr, pivot + 1, right)
def partition(arr, left, right): # 비 균등하게 나눈다.
pivot = arr[left] # 가장 왼쪽의 값을 피벗으로 설정한다
i = left
j = right
print(f"--partition {left=} {right=} --")
print(arr)
print(f"{i=} {j=} pivot = arr[left] = {pivot}")
while i < j:
while pivot < arr[j]:
j -= 1
while i < j and pivot >= arr[i]:
i += 1
print(f"i={i}({arr[i]}) j={j}({arr[j]}) 교환")
arr[i], arr[j] = arr[j], arr[i]
print(arr)
arr[left] = arr[i]
arr[i] = pivot
print(arr, i, f"번({arr[i]}) 기준\n")
return i
quick_sort(arr, 0, len(arr)-1)
"""
left=0 right=13
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
--partition left=0 right=13 --
[1, 4, 0, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=0 j=13 pivot = arr[left] = 1
i=1(4) j=2(0) 교환
[1, 0, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=1(0) j=1(0) 교환
[1, 0, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7] 1 번(1) 기준
left=2 right=13
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
--partition left=2 right=13 --
[0, 1, 4, 6, 8, 3, 2, 5, 7, 3, 5, 8, 7, 7]
i=2 j=13 pivot = arr[left] = 4
i=3(6) j=9(3) 교환
[0, 1, 4, 3, 8, 3, 2, 5, 7, 6, 5, 8, 7, 7]
i=4(8) j=6(2) 교환
[0, 1, 4, 3, 2, 3, 8, 5, 7, 6, 5, 8, 7, 7]
i=5(3) j=5(3) 교환
[0, 1, 4, 3, 2, 3, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7] 5 번(4) 기준
left=2 right=4
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=2 right=4 --
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=2 j=4 pivot = arr[left] = 3
i=4(2) j=4(2) 교환
[0, 1, 3, 3, 2, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7] 4 번(3) 기준
left=2 right=3
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=2 right=3 --
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=2 j=3 pivot = arr[left] = 2
i=2(2) j=2(2) 교환
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7] 2 번(2) 기준
left=6 right=13
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
--partition left=6 right=13 --
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
i=6 j=13 pivot = arr[left] = 8
i=13(7) j=13(7) 교환
[0, 1, 2, 3, 3, 4, 8, 5, 7, 6, 5, 8, 7, 7]
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8] 13 번(8) 기준
left=6 right=12
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8]
--partition left=6 right=12 --
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 8, 7, 8]
i=6 j=12 pivot = arr[left] = 7
i=11(8) j=12(7) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
i=11(7) j=11(7) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8] 11 번(7) 기준
left=6 right=10
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
--partition left=6 right=10 --
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
i=6 j=10 pivot = arr[left] = 7
i=10(5) j=10(5) 교환
[0, 1, 2, 3, 3, 4, 7, 5, 7, 6, 5, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8] 10 번(7) 기준
left=6 right=9
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
--partition left=6 right=9 --
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
i=6 j=9 pivot = arr[left] = 5
i=7(5) j=7(5) 교환
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8] 7 번(5) 기준
left=8 right=9
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
--partition left=8 right=9 --
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
i=8 j=9 pivot = arr[left] = 7
i=9(6) j=9(6) 교환
[0, 1, 2, 3, 3, 4, 5, 5, 7, 6, 7, 7, 8, 8]
[0, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8] 9 번(7) 기준
"""
퀵소트 개선
partition 함수에서 피벗 값이 최소나 최대 값으로 지정되어 파티션이 나누어지지 않을 경우
=> O(N^2)의 시간복잡도를 가진다.배열의 가장 앞의 값(left)과 중간 값(mid == left+right//2)을 교환해주면 확률적으로 시간복잡도를 개선할 수 있다.
=> O(nlog_2n) 하지만 최악의 시간복잡도가 이렇게 되는 것은 아니다.
시간복잡도
- 최선의 경우 = O(nlog_2n)
전체 호출 횟수 (순환 호출의 깊이) = log_2n
각 호출 단계의 비교 연산 = n
=> n * log_2n
- 최악의 경우 = O(N^2)
정렬하려는 배열이 오름차순 또는 내림차순 정렬이 되어있는 경우
전체 호출 횟수 (순환 호출의 깊이) = n
각 호출 단계의 비교 연산 = n
=> n * n
- 평균의 경우 = O(nlog_2n)
공간복잡도
n 크기의 주어진 배열에서 교환을 통해 정렬이 수행된다
=> O(N)
장점
- 불필요한 데이터의 이동을 줄인다, 먼 거리의 데이터를 교환할 수 있다, 한번 결정된 피벗들은 비교에서 제외된다
=> 시간복잡도가 O(nlog2n)으로 다른 정렬 알고리즘 보다 빠르다- 배열 안에서 교환하기 때문에 다른 메모리 공간을 필요로 하지 않는다.
단점
- 불안정 정렬이다.
- 정렬된 배열에 대해서는 불균형 분할로 인해 수행시간이 더 걸린다.
자바의 Arrays.sort() 는 내부적으로 dual pivot quick sort로 구현되어있다.
기술면접에서 빈번히 나오는 주제이다.