정렬

소개 Selection sort(선택 정렬)는 제자리 정렬 알고리즘의 하나로 가장 작은(혹은 가장 큰) 원소를 찾아서 교체하는 알고리즘이다. 말 그대로 원소를 선택해서 정렬한다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Selection sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 우선 인덱스 0을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 1부터 원소 끝까지 순회하면서 가장 작은 원소를 찾는다. 그리고 찾은 원소를 가장 처음 원소와 교체한다. +-----+-----+-----+-----+-----+ | 1 | 4 | 5 | 3 | 2 ..

소개 Cocktail shaker sort(칵테일 셰이커 정렬)는 거품 정렬에서 파생된 정렬 알고리즘이다. 양방향 거품 정렬 혹은 셰이커 정렬 등으로 불린다. 시간 복잡도가 O(n^2)으로 거품 정렬과 비슷하다. 정렬하는 게 마치 칵테일을 위아래로 흔드는 모습과 비슷하다 하여 이런 이름이 붙었다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Cocktail shaker sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 거품 정렬처럼 인덱스 0의 값과 인덱스 1의 값을 비교하는걸 시작으로 인덱스 3의 값과 인덱스 4의 값까지 비교한다. +-----+---..

소개 Bubble sort(거품 정렬)는 인접한 두 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순해서 자주 사용된다. 이름의 유래는 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Bubble sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 우선 인덱스 0의 값과 인덱스 1의 값을 비교하면, 인덱스 0의 값이 더 크기 때문에 두 값이 서로 교체된다. +-----+-----+-----+-----+-----+ | 4 | 5 | 1 | ..