정렬 공통
오름차순이나 내림차순으로 정렬
정렬 종류
선택정렬
삽입정렬
버블정렬
퀵정렬
병합정렬
힙정렬
간접정렬
쉘정렬
분포수세기
기수교환정렬
직접기수정렬
기수정렬
선택정렬
작동방식
비교 대상 원소를 제외한 가장 작은 데이터를 선택해서 비교 대상 원소와 크기 비교 후 조건에
부합할 시 서로의 자리를 바꾼다. 위 과정을 순회를 마칠때까지 반복한다.
시간복잡도
O(N^2)
def selection_sort(arr):
n = len(arr)
for i in range(0, n-1):
cur_index = i
min = arr[cur_index]
min_index = cur_index
for j in range(i+1, n):
if min > arr[j]:
min = arr[j]
min_index = j
arr[cur_index], arr[min_index] = arr[min_index], arr[cur_index]
return arr
class SelectSort {
public void sort(int value[]) {
for (int i = 0; i < value.length; i++) {
int minIndex = i; int min = value[minIndex];
for (int j = i; j < value.length; j++) {
if (value[j] < min) { min = value[j]; minIndex = j;
}
}
swap(value, i, minIndex);
}
printValue(value);
}
private void swap(int array[], int index1, int index2) {
int tempValue = array[index1];
array[index1] = array[index2];
array[index2] = tempValue;
}
private void printValue(int value[]) {
StringBuilder builder = new StringBuilder();
for (int i=0; i < value.length; i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
public class Main {
public static void main(String[] args) {
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
SelectSort algo = new SelectSort();
algo.sort(value);
}
}
삽입정렬
작동방식
오름차순 일 경우 자기 왼쪽의 데이터가 자기보다 크면 두 데이터의 자리를 서로 바꾼다.
그렇지 않을 경우 남아 있는 원소를 순회하여 위 과정을 거친다.
시간복잡도
O(n^2)
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
cur_val = arr[i]
for j in range(i-1, -1, -1):
cmp_val = arr[j]
if cur_val < cmp_val:
arr[i], arr[j] = arr[j], arr[i]
i = j
else:
break
return arr
class InsertionSort {
public void Sort(int arr[]) {
for(int i = 1; i < arr.length; i++) {
int cur_val = arr[i];
for (int j = i-1; j >= 0; j--) {
int cmp_val = arr[j];
if (cur_val < cmp_val) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i = j;
}
else break;
}
}
printValue(arr);
}
private void printValue(int arr[]) {
StringBuilder builder = new StringBuilder();
for(int i = 0; i < arr.length; i++) {
builder.append(arr[i]).append(' ');
}
System.out.println(builder.toString());
}
}
public class Main {
public static void main(String[] args) {
int arr[] = {5,4,3,2,1};
InsertionSort algo = new InsertionSort();
algo.Sort(arr);
}
}
버블정렬(거품정렬)
작동방식
오름차순의 경우 좌측에 위치한 값이 자신보다 클 경우 두 데이터의 위치를 서로 바꾼다.
시간복잡도
O(N^2)
def bubble_sort(arr):
n = len(arr)
for i in range(0, n-1):
cur_val = arr[i]
for j in range(i+1, n):
cmp_val = arr[j]
if cur_val > cmp_val:
arr[i], arr[j] = arr[j], arr[i]
cur_val = arr[j]
else:
break
return arr
class BubbleSort {
public void Sort(int arr[]) {
for (int i = 0; i < arr.length -1; i++) {
int cur_val = arr[i];
for (int j = i+1; j < arr.length; j++) {
int cmp_val = arr[j];
if (cur_val > cmp_val) {
swap(arr, i, j);
} else break;
}
}
printValue(arr);
}
private void swap(int arr[], int idx1, int idx2) {
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
private void printValue(int arr[]) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]).append(' ');
}
System.out.println(builder.toString());
}
}
public class Main {
public static void main(String[] args) {
int arr[] = {10,9,8,7,6,5,4,3,2,1};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.Sort(arr);
}
}
퀵정렬
작동방식
pivot(정하기 나름) 기준으로 작은 데이터는 좌측에 큰 데이터는 우측에 배치한다.
좌측 및 우측에 배치한 데이터를 나눌 수 있을 때까지 재귀적으로 위 과정을 실행한다.
시간복잡도
O(nlogn), 단 최악의 경우(pivot이 가장 크거나 가장 작으면 모든 데이터를 비교해야 함)
import random
def q_sort(arr):
if len(arr) < 1:
return arr
pivot = arr[0]
left, right = list(), list()
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return q_sort(left) + [pivot] + q_sort(right)
arr = random.sample(range(100), 10)
퀵소트 파이썬의 리스트 컴프리핸션을 통해 표현한 방법
def q_sort(arr):
if len(arr) < 1:
return arr
pivot = arr[0]
left = [item for item in arr[1:] if pivot > item]
right = [item for item in arr[1:] if pivot <= item]
return q_sort(left) + [pivot] + q_sort(right)
병합정렬
작동 방식
먼저 배열의 길이가 1이 될때 까지 배열을 나누는 작업을 실시한 후 다 나누어 졌을 때 나뉜 배열을 다시 서로
합치는 과정을 거친다. 이 때 배열의 길이가 N일 때 logN만큼 분할 하는 과정을 거치고 N번 만큼 병합하는 과
정을 거치므로 O(NlogN)의 시간 복잡도를 가진다.
시간복잡도
O(nlogn)
정렬 참고 링크
