가장 기본적인 정렬 알고리즘으로 버블정렬, 선택정렬, 삽입정렬을 들 수 있다.
빅오표기법에 따르면 O(N^2)의 시간복잡도를 가진다.
java로 이 세가지 정렬 알고리즘을 구현해보자.
📁 버블정렬 Bubble Sort
인접한 두 원소의 값을 비교하여 자리를 교환하는 정렬 알고리즘
버블정렬은 비교와 교환 두 종류의 단계를 거친다.
⏳ 과정
- 인접한 두 원소의 값을 비교한다.
- 두 값의 순서가 바뀌어 있을 경우, 교환(swap)한다.
1~2의 패스스루가 끝나면 정렬되지 않은 값 중 가장 큰 값, 즉 '버블'이 맨 오른쪽 위치로 이동한다.
따라서 다음 패스스루는 제대로 정렬된 마지막 인덱스를 제외하고 이루어진다.
💻 소스코드
static void bubbleSort(int[] arr) {
int temp;
// 패스스루 횟수. n-1회만큼 진행
for (int i=0 ; i<arr.length-1 ; i++) {
for (int j=0 ; j<arr.length-i-1 ; j++) {
// 인접한 두 원소를 비교, 필요한 경우 교환
if (arr[j] > arr[j+1]) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}📁 선택정렬 Selection Sort
특정 인덱스에 들어갈 원소를 찾아 선택하는 정렬 알고리즘
버블정렬과 마찬가지로 비교와 교환 두가지의 단계를 거친다.
⏳ 과정
- 배열에서 최솟값을 찾는다.
- 첫 인덱스가 최솟값이 아닐경우, 최솟값이 들어있는 인덱스와 교환한다.
한 차례의 패스스루 이후 첫 인덱스는 최솟값이 된다.
따라서 다음 패스스루는 첫번째 인덱스를 제외하고 이루어진다.
💻 소스코드
static void selectionSort(int[] arr) {
int temp;
int lowestNumIndex;
// 패스스루 횟수는 n-1
for (int i=0 ; i<arr.length-1 ; i++) {
lowestNumIndex=i;
// 최솟값을 갖는 원소 찾기
for (int j=i ; j<arr.length ; j++) {
if (arr[j]<arr[lowestNumIndex]) {
lowestNumIndex=j;
}
}
// 시작 인덱스가 최솟값을 가지지 않을 경우, 최솟값을 가진 인덱스와 교환
if (lowestNumIndex!=i) {
temp=arr[i];
arr[i]=arr[lowestNumIndex];
arr[lowestNumIndex]=temp;
}
}
}📁 삽입정렬 Insertion Sort
특정 인덱스와 그 이전의 원소들을 비교해 올바른 자리에 삽입하는 정렬 알고리즘
비교, 시프트, 삽입, 삭제 네 단계를 포함한다.
⏳ 과정
- 타겟이 되는 인덱스의 값을 삭제하고, 이 값을 임시변수에 저장한다.
- 비어 있는 인덱스 왼쪽에 있는 값을 타겟과 비교한다.
- 왼쪽이 타겟보다 큰 경우, 그 값을 오른쪽으로 시프트한다.
- 왼쪽에 원소가 없거나 왼쪽 원소가 타겟보다 크지 않을 때까지 1~3의 과정을 반복한다.
- 임시변수에 있는 값을 공백 인덱스에 저장한다.
패스스루가 끝나면 인덱스 0부터 타겟까지의 원소들은 (그들끼리는) 제대로 정렬된 상태이다.
따라서 다음 패스스루는 타겟의 오른쪽 원소를 어디에 삽입할지 결정하는 과정이다.
타겟의 오른쪽 인덱스를 새로운 타겟으로 하여 1~5의 과정을 반복한다.
💻 소스코드
static void insertionSort(int[] arr) {
int target;
int j;
// 왼쪽에 비교할 원소가 있어야 하므로, 타겟의 인덱스는 1부터 시작한다.
for (int i=1 ; i<arr.length ; i++) {
target=arr[i];
j=i-1;
// 타겟이 왼쪽 원소보다 작을 경우, 왼쪽 원소를 시프트한다.
while (j>=0 && arr[j]>target) {
arr[j+1]=arr[j];
j--;
}
// 임시변수에 저장된 값을 빈 인덱스에 저장한다.
arr[j+1]=target;
}
}