특정 값을 기준으로 데이터를 순서대로 배치하는 방법이다.
정렬도 난이도와 속도에 따라 여러가지로 나눌 수 있다. 이번에는 그 중에서 구현난이도가 쉽지만 속도는 느린 버블 정렬, 삽입 정렬, 선택 정렬에 대해 구현법을 알아봤다. 이 세가지 정렬 방법은 swap하는데 필요한 tmp변수가 사용하는 메모리 말고는 추가적인 메모리를 사용하지 않는 inplace정렬법이다! 그래서 구현하기는 쉽지만 속도는 느리다. (메모리 사용량과 속도는 반비례관계가 있다.)
버블 정렬은 인접한 데이터를 비교하며 자리를 바꾸는 방식이다.
1번 정렬할 때마다 가장 큰 값의 위치가 정해진다(오름차순).
해당 인덱스와 그 이전 인덱스를 비교했을 때, 이전 인덱스가 더 크면 두 값을 교환한다.
다양한 방법으로 구현할 수 있지만 인덱스만 신경써서 잘 나타내 주면 된다!
// 버블 정렬 오름차순
public static void bubbleSort(int[] arr) {
// 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]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
// 1.
for(int i = 1; i<arr.length-1; i++){
for(int j = 0; j < arr.length-i; j++){
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
// 2. 1과 같은 방법이지만 i인덱스 다르게 사용!
for(int i = arr.length-1; i>0; i--){
for(int j = 0; j<i; j++){
if(arr[j]>arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
};
}
}
// 3. 이 코드가 가장 그림과 유사
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 1; j <= i; j++) {
if (arr[j-1] > arr[j]) {
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
}
앞의 데이터를 정렬해 가면서 삽입 위치를 찾아 정렬하는 방식이다.
해당위치의 데이터가 바로 자신의 위치를 찾아가기 때문에 이전의 모든 데이터는 오름차순으로 정렬된 상태를 가지게 된다.
// 삽입 정렬 오름차순
public static void insertionSort(int[] arr) {
for(int i = 1; i<arr.length; i++){
for(int j = i; j>0; j--){
if(arr[j] < arr[j-1]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
} else{
break;
}
}
}
}
최소 또는 최대 값을 찾아 가장 앞 또는 뒤부터 정렬하는 방식이다.
// 선택 정렬 오름차순
private static void selectionSort(int[] arr) {
// 1. 최솟값을 찾아 앞부터 교환
for(int i = 0; i < arr.length-1; i++){
int min = i; // 최솟값이 위치할 자리
for(int j = i+1; j < arr.length; j++){
if(arr[min] > arr[j]){
min = j; // 최소값이 위치한 인덱스
}
}
int tmp = arr[min]; // 최솟값과 최솟값이 위치해야 할 자리의 값을 스왑하여 최솟값을 앞쪽에 둠
arr[min] = arr[i];
arr[i] = tmp;
}
//2. 최댓값을 찾아 뒤부터 교환
for(int i = arr.length-1; i>0; i--){
int max = i; // 최댓값이 위치할 자리
for(int j = i-1; j>=0; j--){
if(arr[max] < arr[j]){
max = j; // 최댓값이 위치한 인덱스
}
}
int tmp = arr[i]; // 최댓값을 최댓값이 위치해야할 자리로 옮기기 위해 스왑 한다.
arr[i] = arr[max];
arr[max] = tmp;
}
}
정렬을 구현할 때에는 인덱스 값을 신경을 써주자!