- 비교 연산이 필요한 루프 범위를 설정한다.
- 인접한 데이터 값을 비교한다.
- swap 조건에 부합하면 swap 연산을 수행한다.
- 루프 범위가 끝날 때까지 2~3번을 반복한다.
- 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
- 비교 대상이 없을 때까지 1~5를 반복한다.
public class BubbleSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N - i; j++) {
if (A[j] > A[j + 1]) {
int temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
}
for (int i = 0; i < N; i++) {
System.out.println(A[i]);
}
}
}
}
- 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
- 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
- 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬의 범위를 축소한다.
- 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.
- 현재 index에 있는 데이터 값을 선택한다.
- 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
- 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.
- 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.
- 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.
적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
- 데이터를 분할하는 pivot(기준점)을 설정한다.
- pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리한다.
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
- end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end 가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.
- start와 end가 만날 때까지 위를 반복한다.
- start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.
- 분리 집합에서 각각 다시 pivot을 선정한다.
- 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복한다.
- 정렬할 그룹을 최소 길이로 나눈다.
- 나눈 그룹마다 병합 정렬한다.
- 이어서 병합된 그룹을 대상으로 정렬한다.
2개의 그룹을 병합하는 과정
- 투포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
- 왼쪽 포인터와 오른쪽 포인터 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
import java.io.*;
public class BaekJoon2751 {
public static int[] A, tmp;
public static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
A = new int[N + 1];
tmp = new int[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = Integer.parseInt(br.readLine());
}
merge_sort(1, N);
for (int i = 1; i <= N; i++) {
bw.write(A[i] + "\n");
}
bw.flush();
bw.close();
}
private static void merge_sort(int s, int e) {
if (e - s < 1)
return;
int m = s + (e - s) / 2;
merge_sort(s, m);
merge_sort(m + 1, e);
for (int i = s; i <= e; i++) {
tmp[i] = A[i];
}
int k = s;
int index1 = s;
int index2 = m + 1;
while (index1 <= m && index2 <= e) {
if (tmp[index1] > tmp[index2]) {
A[k] = tmp[index2];
k++;
index2++;
} else {
A[k] = tmp[index1];
k++;
index1++;
}
}
while (index1 <= m) {
A[k] = tmp[index1];
k++;
index1++;
}
while (index2 <= e) {
A[k] = tmp[index2];
k++;
index2++;
}
}
}
핵심 이론
- 일의 자릿수 기준으로 원소를 큐에 집어넣는다.
- 0번째 큐부터 9번째 큐까지 pop을 진행한다.
- 이어서 십의 자릿수를 기준으로 같은 과정을 진행한다.
- 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다.
import java.io.*;
public class BaekJoon10989 {
public static int[] A;
public static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
br.close();
radixSort(A, 5);
for (int i = 0; i < N; i++) {
bw.write(A[i] + "\n");
}
bw.flush();
bw.close();
}
public static void radixSort(int[] A, int maxSize) {
int[] output = new int[A.length];
int jarisu = 1;
int count = 0;
while (count != maxSize) { // 최대 자리수만큼 반복하기
int[] bucket = new int[10];
for (int i = 0; i < A.length; i++) { // 일의 자리부터 시작하기
bucket[(A[i] / jarisu) % 10]++;
}
for (int i = 1; i < 10; i++) { // 합 배열을 통해 index 계산하기
bucket[i] += bucket[i - 1];
}
for (int i = A.length - 1; i >= 0; i--) { // 현재 자리수를 기준으로 정렬하기
output[bucket[(A[i] / jarisu & 10)] - 1] = A[i];
bucket[(A[i] / jarisu) % 10]--;
}
for (int i = 0; i < A.length; i++) {
// 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장하기
A[i] = output[i];
}
jarisu *= 10; // 자릿수 증가시키기
count++;
}
}
}