1. 버블 정렬(Bubble Sort)
- 첫 번째 요소와 두 번째 요소를 비교하여 필요한 경우 자리를 바꿉니다.
- 두 번째 요소와 세 번째 요소를 비교하여 필요한 경우 자리를 바꿉니다.
- 리스트의 끝까지 이 과정을 반복합니다.
- 리스트의 끝까지 한 번의 턴이 끝나면 가장 큰 요소가 리스트의 끝에 위치하게 됩니다.
- 이 과정을 리스트의 모든 요소가 정렬될 때까지 반복합니다.
소스코드
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j]<arr[j-1]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
이미지 출처
2. 선택 정렬 (Selection Sort)
-
처음부터 끝까지 순차적으로 탐색하며, 각 턴에서 현재 턴의 데이터들 중 가장 작은 값을 찾습니다.
-
현재 턴의 맨 앞 데이터는 이미 정렬이 완료된 상태로 간주합니다. 따라서 다음 턴에서는 그 다음 데이터부터 마지막 데이터까지 동일한 과정을 반복합니다.
소스 코드
void selectionSort(int[] list) {
int indexMin, temp;
for (int i = 0; i < list.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[indexMin]) {
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
이미지 출처
3. 삽입정렬(insertion sort)
-
첫 번째 요소는 이미 정렬된 것으로 간주합니다.
-
두 번째 요소부터 마지막 요소까지 순차적으로 각 요소를 앞의 정렬된 부분과 비교하여 적절한 위치에 삽입합니다.
소스코드
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){
int temp = arr[index];
int aux = index - 1;
while( (aux >= 0) && ( arr[aux] > temp ) ) {
arr[aux + 1] = arr[aux];
aux--;
}
arr[aux + 1] = temp;
}
}
이미지 출처
4. 비교
버블 정렬
작동 방식: 인접한 원소끼리 비교하여 교환하는 방식으로, 가장 큰 원소를 맨 뒤로 보내는 과정을 반복합니다.
- 단순함이 요구되지만 성능이 중요하지 않은 경우에 사용합니다.
선택 정렬
작동 방식: 배열에서 최솟값을 찾아서 맨 앞으로 이동시키는 과정을 반복합니다.
- 교환 횟수가 적어, 메모리 사용을 최소화해야 하는 경우에 유리합니다.
삽입 정렬
작동 방식: 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 올바른 위치에 삽입하는 방식입니다.
- 셋 중 가장 빠르며, 대부분의 데이터가 이미 정렬된 상태에서 사용하면 유리합니다.
시간 복잡도: 세 알고리즘 모두 평균적으로 O(n²)의 시간 복잡도를 가집니다.
ref.
https://scksk.tistory.com/25
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC
https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC
https://velog.io/@minji0801/버블정렬-vs-선택정렬-vs-삽입정렬-차이-제대로-알고가자
