선택 정렬
- 현재 위치에 들어갈 데이터 찾아 선택하는 알고리즘
비교 정렬- 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 X ->
제자리 정렬 (in-place sort) - 정렬 규칙이 다수거나 특정 순서 유지해야하는 상황에서는 문제 ->
불안정 정렬 - 성능상 좋진 않음 ..
과정은 다음과 같다.
- 주어진 리스트에서 최솟값을 찾는다.
- 최솟값을 맨 앞 자리의 값과 교환한다.
- 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다.
- 시간 복잡도 :
O(N^2)
((N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1) = N(N-1)/2
코드
public class selectionSort {
public static void main(String[] args) {
int[] a = { 3, 5, 1, 2, 4 };
int tempValue, tempJ = 0;
for (int i = 0; i < a.length - 1; i++) { // 배열 처음부터 끝까지 반복 (i는 현재 위치)
int min = Integer.MAX_VALUE; // 제일 작은 수를 찾기 위해, min은 int의 최대 값으로 임시 세팅
for (int j = i + 1; j < a.length; j++) {
if (a[j] < min) { // 현재 위치부터 배열 마지막까지 반복문 돌면서 최소 값을 계속 찾음
min = a[j];
tempJ = j;
}
}
tempValue = a[i]; // 찾은 최소값과 현재 위치의 값과 서로 바꿈
a[i] = a[tempJ];
a[tempJ] = tempValue;
}
System.out.println(Arrays.toString(a));
}
}버블 정렬
-
비교 정렬&제자리 정렬&안정 정렬 -
바로 오른쪽 옆에 있는 숫자와 크기 비교 -> 서로 자리를 바꿔가며 정렬하는 방법
-
배열의 뒷쪽부터 정렬됨.
-
시간 복잡도 :
O(N^2)
((N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1) = N(N-1)/2
코드
public class bubbleSort {
public static void main(String[] args) {
int[] a = { 3, 5, 1, 2, 4 };
int tempValue;
for (int i = 0; i < a.length; i++) { // 라운드 수
for (int j = 0; j < a.length - i - 1; j++) { // 각 라운드별 비교 횟수
if (a[j] > a[j + 1]) {
tempValue = a[j];
a[j] = a[j + 1];
a[j + 1] = tempValue;
}
}
}
System.out.println(Arrays.toString(a));
}
}삽입 정렬
- 현재 비교하고자 하는 타겟과 그 이전의 원소들과 비교하며 자리를 교환하는 방법
비교 정렬&제자리 정렬&안정 정렬
과정은 다음과 같다.
- 현재의 타겟이 되는 숫자와 이전 위치의 원소들을 비교한다.
- 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
- 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.
- 시간 복잡도 :
O(N^2)
((N-1) + (N-2) + (N-3) + ... + 3 + 2 + 1) = N(N-1)/2
코드
public class insertionSort {
public static void main(String[] args) {
int[] a = { 3, 5, 1, 2, 4 };
int tempValue, target;
for (int i = 1; i < a.length; i++) {
tempValue = a[i]; // 선택된 숫자를 임시 저장
target = i - 1; // 비교 대상의 위치
while (target >= 0 && a[target] > tempValue) { // 왼쪽 끝까지 가거나, 자신보다 작은 수를 만나기 전까지 이동하면 삽입될 위치를 찾음
a[target + 1] = a[target]; // 나보다 큰 수는 오른쪽으로 한칸 이동
target--; // 그 다음 비교대상을 왼쪽으로 한 칸 이동
}
a[target + 1] = tempValue; // 적정한 위치를 찾아 선택된 숫자를 삽입
}
System.out.println(Arrays.toString(a));
}
}퀵 정렬
-
하나의
피벗 (pivot)기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 부분리스트, 다른 하나는 피벗보다 큰 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 재귀적으로 수행하는 알고리즘 -
비교 정렬&제자리 정렬&불안정 정렬 -
피벗은 중간 값으로 잡는 게 가장 좋다..
과정은 다음과 같다.
- 피벗을 하나 선택한다.
- 피벗 기준 -> 양쪽에서 피벗보다 큰 값 or 작은 값을 찾는다. 왼쪽에서부터는 큰 값, 오른쪽에서부터는 작은 값을 찾는다.
- 양 방향에서 찾은 두 원소를 교환한다.
- 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2번으로 돌아가 반복한다.
- 엇갈린 기점 기준 -> 두 개의 부분리스트로 나눠 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때까지 1번 과정 반복한다. (Divide : 분할)
- 인접한 부분리스트끼리 합친다. (Conqure : 정복)
- 시간 복잡도 : 평균 -
O(N^2), 최악 -O(N^2)
코드
public class QuickSort {
// 배열(data)의 요소 data[pl]과 data[pr] 교환
static void swap(int[] data, int pl, int pr) {
int temp = data[pl];
data[pl] = data[pr];
data[pr] = temp;
}
static void quickSort(int[] data, int left, int right) { // left, right는 각 커서의 시작점
int pl = left;
int pr = right;
int pivot = data[(pl + pr) / 2]; // 피벗은 각 끝의 커서의 중간 값으로 선택
do {
while (data[pl] < pivot) { // data[pl] 값이 pivot보다 큰 수 탐색
pl++;
}
while (data[pr] > pivot) { // data[pr] 값이 pivot보다 작은 수 탐색
pr--;
}
if (pl <= pr) { // pl보다 pr이 크면 교환(오름차순)
swap(data, pl++, pr--);
}
} while (pl <= pr);
// 정렬 끝난 후 나누어진 두개의 그룹에 데이터 수를 체크
if (left < pr)
quickSort(data, left, pr); // left가 pr보다 작으면 그룹의 수가 1개 이상이기 때문에 다시 정렬
if (pl < right)
quickSort(data, pl, right); // pl이 right보다 작으면 그룹의 수가 1개 이상이기 때문에 다시 정렬
}
public static void main(String[] args) {
int[] x = { 5, 7, 1, 4, 6, 2, 3, 9, 8 };
quickSort(x, 0, x.length - 1);
for(int i = 0 ; i < x.length ; i++) {
System.out.println(x[i]);
}
}
}or
public class Test {
private static void quickSort(int[] arr){
quickSort(arr, 0, arr.length - 1); // 시작 위치와 끝나는 위치를 받아서 재귀 함수를 호출해줌
}
private static void quickSort(int[] arr, int start, int end){
int part2 = partition(arr, start, end); // 배열의 시작과 끝 영역 안에서 파티션을 나눔 -> 나눈 파티션의 오른쪽 방 첫 번째 값(인덱스)을 받아옴
/*
오른쪽 파티션이 시작점 바로 다음에서 시작(== 오른쪽 파티션이 시작점에서 한 개 차이) -> 왼쪽 파티션의 데이터가 하나(쏠려있는 현상인 경우) ==> 더 이상 정렬할 필요가 없음
[3, 5, 4, 2, 1]인 경우
[ 3 | 5, 4, 2, 1]
smaller | bigger
=> smaller 파티션의 값이 하나이므로 정렬할 필요가 없음.
*/
if(start < part2 - 1){ // 오른쪽 파티션이 시작점에서 한 개 이상 차이가 날 때만(쏠려있지 않은 경우에만) 함수를 재귀적으로 호출하게 함
quickSort(arr, start, part2 - 1); // 시작과 끝 점을 조정해서 재귀 호출. part2가 오른쪽 방 첫 번째 값이니까 (part2 - 1)은 왼쪽 방의 마지막 인덱스 값
}
if(part2 < end){ // 오른쪽 배열방의 값이 2개 이상일 때만 호출 ==> 오른쪽 파티션의 시작점이 배열의 마지막 값보다 작은 경우에만 재귀 함수 호출
// 오른쪽 파티션의 시작점 == 배열의 마지막 값 -> 오른쪽 배열의 값이 하나 있고 그 값이 시작점 값임. 따라서 이런 경우에는 정렬할 필요가 없으니까 이러한 경우를 제외할 때만 재귀함수를 호출해야 한다.
quickSort(arr, part2, end);
}
}
private static int partition(int[] arr, int start, int end){
int pivot = arr[(start + end) / 2]; // 기준점: 배열의 처음과 끝 값의 중간지점
while(start <= end){ // 시작점이 끝점보다 작거나 같을 때만 시작점을 앞으로 한칸씩 옮김
while(arr[start] < pivot) start++; // 배열방의 값이 피벗값보다 작은 경우에(정상적인 경우) 시작점을 한 칸씩 옮김(통과)
while(arr[end] > pivot) end--; // 배열방의 값이 피벗 값보다 클 경우에만(정상적인 경우) 끝점을 한 칸씩 옮김(통과)
if(start <= end){ // 시작점이 끝점을 지나쳤는지 다시 한번 확인해준 후에
swap(arr, start, end); // 두 점을 바꿔줌(시작점이 피벗 값보다 큰 경우 + 끝점이 피벗 값보다 작은 경우)
start++; // 시작점을 한칸씩 옮김
end--; // 끝점을 한칸씩 옮김
}
}
return start; // 새로 나눌 오른쪽 파티션의 첫 번째 배열방 인덱스를 반환
}
private static void swap(int[] arr, int start, int end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
private static void printArray(int[] arr){ // 배열 확인용 출력 메소드
for(int data : arr){
System.out.print(data + " ,");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
printArray(arr);
quickSort(arr);
printArray(arr);
}
}💡 참고
https://st-lab.tistory.com/250
https://turtledeveloper.tistory.com/41
https://kim-oriental.tistory.com/15
