CS/알고리즘

퀵 정렬 (Quick Sort)

기준이 되는 요소(pivot)을 하나 정해서 그 요소를 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아넣고 그것들을 다시 반복해서 정렬하여 합치는 알고리즘이다.(divide and conquer) 시간 복잡도 Best - O(NlogN) Average - O(NlogN) Worst - O(N^2) 설명 pivot을 하나 정한다. 그 후에 시작과 끝의 인덱스를 각각 left와 right로 정한다. left는 pivot보다 큰 요소를 찾을 때까지 증가시킨다. right는 pivot보다 작은 요소를 찾을 때까지 감소시킨다. 만약 left가 pivot보다 큰 요소를 찾았고 right가 pivot보다 작은 요소를 찾았다면 서로 자리를 바꿔준다. 그런데 만약 이 때 left와 right가 서로 교차하여 le..

삽입 정렬 (Insertion Sort)

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 방법이다. 시간 복잡도 Best - O(N) Average - O(N^2) Worst - O(N^2) 설명 삽입 정렬은 길이가 n인 배열에서 인덱스가 1번인 요소(두 번째 요소)부터 시작한다. 배열에서 요소를 선택해서 이전 인덱스의 요소들과 비교하여 적절한 위치에 삽입한다. 이를 n - 1번 반복하면 오름차순 또는 내림차순으로 정렬을 완성할 수 있다. 구현(파이썬) arr = [6, 5, 3, 1, 8, 7, 2, 4] for i in range(1, len(arr)): for j in range(i, 0, -1): # 오름차순 기준, 내림차순은 부호를 반대로 if arr[j - 1..

선택 정렬 (Selection Sort)

선택된 값과 나머지 데이터들을 전부 비교하여 알맞은 자리를 찾는 방법이다. 시간 복잡도 Best - O(N^2) Average - O(N^2) Worst - O(N^2) 설명 길이가 n인 배열에서 인덱스가 0번인 자리를 선택하고, 해당 인덱스를 최솟값을 가지는 인덱스로 둔다. 그 후에 배열의 끝까지 탐색하며 최솟값을 가지는 인덱스를 찾는다. 탐색이 완료되면, 선택한 인덱스 0번의 요소와 최솟값을 맞바꾼다. 이후 인덱스가 1번인 자리를 선택하고 그 이후의 요소들을 가지고(이전 인덱스는 이미 정렬했기 때문에 탐색하지 않는다.) 최솟값을 탐색한 다음 다시 최솟값을 맞바꾼다. 이를 n - 1번 반복하면 오름차순 정렬이 완료된다. 구현(파이썬) arr = [29, 10, 14, 37, 20, 25, 44, 15]..

버블 정렬 (Bubble Sort)

버블 정렬은 아주 기본적인 정렬 알고리즘이지만 시간 복잡도때문에 실제로는 잘 사용하지 않는 알고리즘이다. 시간 복잡도 Best - O(N^2) Average - O(N^2) Worst - O(N^2) 설명 버블정렬은 인접한 두 요소를 비교하여 큰 요소를 오른쪽으로 보내는 정렬 방법이다. 이렇게 배열을 한 바퀴 돌면 맨 끝에 제일 큰 요소가 하나 고정된다. 이를 길이가 n인 배열에서 고정된 요소들을 제외하고 n - 1 번 반복하면 최종적으로 모든 요소가 오름차순으로 정렬된다. 구현(파이썬) arr = [5, 1, 4, 2, 8] for i in range(len(arr) - 1, 0, -1): for j in range(i): # 오름차순 기준, 내림차순은 부호를 반대로 if arr[j] > arr[j +..