정렬이란?
- 데이터를 특정한 기준에 따라 순서대로 나열하는 것
- 키 값이 작은 작은 데이터를 앞쪽에 넣으면 오름차순(ascending order)정렬, 그 반대로 놓으면 내림차순(descending order)정렬
- 정렬 알고리즘의 핵심요소는 교환, 선택, 삽입이다.
| 내부정렬 | 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 |
| 외부정렬 | 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘 |
1. 버블정렬(Bubble Sort)
- 오름차순 또는 내림차순으로 정렬할 때 인접한 데이터 두개의 대소 관계를 비교해서 크기 순서대로 교환하는 작업
- 오름차순으로 정렬할 경우 왼쪽값이 오른쪽 값보다 작아야 한다.
예제) 버블정렬을 구현한 코드
1) 버블정렬을 구현하는 mySort()메서드 생성, 2) 데이터를 교환하는 swap()메서드 생성
public class ArrayBubbleSort {
public static void swap(int a[], int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 버블정렬: 오름차순 데이터배열, 데이터수
public static void mySort(int a[], int n) { // 제일 작은 값이 제일 앞에
// 이중 for문
for (int i = 0; i < n-1; i++) { // 배열의 크기만큼 for문 실행
for (int j = n-1; j>i; j--) { // 배열안의 인접한 숫자 비교(뒤에서부터 비교)
if (a[j-1] > a[j]) { // 부등호 표시만 바꾸면 내림차순
swap(a, j-1, j); // 배열, 앞의 값, 뒤의 값
}
}
}
}
3) 전체 코드
package al03_sort;
import java.util.Arrays;
import java.util.Random;
public class ArrayBubbleSort {
public static void swap(int a[], int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 버블정렬: 오름차순 데이터배열, 데이터수
public static void mySort(int a[], int n) { // 제일 작은 값이 제일 앞에
// 이중 for문
for (int i = 0; i < n-1; i++) { // 회차
for (int j = n - 1; j > i; j--) {
if (a[j-1] > a[j]) {
swap(a, j-1, j);
}
}
}
}
public static void main(String[] args) {
// 데이터 준비
// 1~100까지의 난수를 생성해 크기순으로 정렬(오름차순)
Random ran = new Random();
int arr[] = new int[10]; // 10개의 정수를 저장할 수 있는 배열 생성
for(int i=0; i<arr.length; i++) {
arr[i] = ran.nextInt(100)+1; // 1~100까지
}
System.out.println("정렬전 -> " + Arrays.toString(arr));
mySort(arr, arr.length);
System.out.println("정렬후 -> " + Arrays.toString(arr));
}
}
<출력결과>
정렬전 -> [71, 1, 93, 96, 95, 3, 15, 38, 52, 93]
정렬후 -> [1, 3, 15, 38, 52, 71, 93, 93, 95, 96]
2. 선택정렬(Selection Sort)
- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
- 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 해서 시간복잡도가 O(N^2)로 된다.
*의사코드*
for i = 0 to n:
a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
a[i]와 a[j]의 값을 서로 맞바꾼다.
예제) 선택 정렬 소스 코드
public class Main {
public static void main(String[] args) {
// 선택 정렬
int n = 10;
int[] arr = {7,5,9,0,3,1,6,4,2,8};
for(int i=0; i<n; i++) {
int min_index = i;
for(int j=i+1; j<arr.length; j++) {
if(arr[min_index]>arr[j]) {
min_index = j;
}
}
int tmp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = tmp;
}
for(int i=0;i<n;i++) {
System.out.print(arr[i] + " ");
}
}
}3. 삽입정렬(Insertion Sort)
- 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복해 정렬하는 알고리즘
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
- 삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
- 삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.(최선의 경우 O(N)의 시간복잡도를 가짐)
예제) 삽입정렬을 소스 코드
public class Main2775 {
public static void main(String[] args) {
// 삽입 정렬
int n = 10;
int[] arr = {7,5,9,0,3,1,6,4,2,8};
for(int i=1; i<n; i++) { // 인덱스 i부터 1까지 감소하며 반복하는 문법
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; // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
}
}
for(int i=0; i<arr.length;i++)
System.out.print(arr[i] + " ");
}
}
1) 삽입정렬을 구현하는 mySort()메서드 생성
static void mySort(int a[],int n) {
for(int i=1; i<n; i++) { // 1,2,3,4,5,6,7,8,9
int temp = a[i]; // 1번째 인덱스 (0번째 인덱스와 비교해야 함)
int j;
for(j=i; j>0 && a[j-1] > temp; j--) { // 검색하려는 수가 클 때만 비교
a[j] = a[j-1];
}
a[j] = temp;
}
}
2) 전체 코드
package al03_sort;
import java.util.Arrays;
import java.util.Random;
public class ArrayInsertionSort {
// 삽입정렬(Insertion Sort)
static void mySort(int a[],int n) {
for(int i=1; i<n; i++) { // 1,2,3,4,5,6,7,8,9
int temp = a[i]; // 1번째 인덱스 (0번째 인덱스와 비교해야 함)
int j;
for(j=i; j>0 && a[j-1] > temp; j--) { // 검색하려는 수가 클 때만 비교
a[j] = a[j-1];
}
a[j] = temp;
}
}
public static void main(String[] args) {
Random r = new Random();
int a[] = new int[10];
for(int i=0;i<a.length;i++) {
a[i] = r.nextInt(100); // 0~99
}
System.out.println("정렬전 -> " + Arrays.toString(a));
mySort(a,a.length);
System.out.println("정렬후 -> " + Arrays.toString(a));
}
}4. 퀵 정렬(Quick Sort)
- 일반적으로 사용되고 있는 빠른 정렬 알고리즘
- 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- 가장 기본적인 퀵 정렬은 첫 번째 데이터로 기준 데이터(Pivot)로 설정한다.
- 퀵정렬은 대표적인 '분할 정복' 알고리즘으로 평균속도가 O(N*log N)이다. (하지만 항상 N*logN은 아니고 pivot값에 따라 최악 시간 복잡도는 O(N^2)가 될 수 있다.예)이미 정렬이 되어 있는 경우)
배열을 두 그룹으로 나누기
- 왼쪽 끝 요소의 인덱스 pl / 피벗 X / 오른쪽 끝 요소의 인덱스 pr
- 그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 이상의 배열을 오른쪽으로 옮겨야 한다.
| a[pl] >= X 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔 | X보다 큰 값을 찾으면 오른쪽으로 보내야 한다. |
| a[pr] <= X가 가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔 | X보다 작은 값을 찾으면 왼쪽으로 보내야 한다. |
- pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점이고, pr이 위치한 지점은 피벗 값 이하의 요소가 있는 지점이다.
- 여기서 왼쪽(pl)과 오른쪽(pr)이 가리키는 인덱스 a[pl] <-> a[pr]의 값을 교환한다.
- 그러면 피벗 이하의 값은 왼쪽으로 이동하고, 피벗 이상의 값은 오른쪽으로 이동한다.
-> 3이 7이 있는 인덱스[1]으로 가고, 7이 3이 있는 인덱스[6]으로 간다.
-> 계속해서 스캔하면 결국 두 그룹으로 나뉘어 지게 된다.
예제) 퀵 정렬의 소스 코드
package al03_sort;
import java.util.Arrays;
public class QuickSort {
// 배열요소 a[idx1]과 a[idx2]의 값을 바꾼다.
public static void swap(int a[], int idx1, int idx2) {
int tmp = a[idx1]; // 무엇을 먼저 하든 순서는 상관없음
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 배열, 시작 인덱스, 끝인덱스
public static void myQuick(int[] a, int left, int right) {
int pl = left; // 왼쪽부터 검색할 index위치
int pr = right; // 오른쪽부터 검색할 index위치 (인덱스 중의 제일 큰 값)
int pivot = a[(left + right) / 2]; // 피벗위치의 값을 구하기(기준) ((0+2)/7))
// p1과 pr이 만날때까지, 배열 나누기
do {
while (a[pl] < pivot)
pl++;
while (a[pr] > pivot)
pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
// 정렬 후 왼쪽을 재정렬할 재귀호출
if(left<pr)
myQuick(a,left,pr);
// 정렬 후 오른쪽을 재정렬할 재귀호출
if(pl<right)
myQuick(a,pl,right);
}
while (a[pl] < pivot) pl++;
- 피벗기준 왼쪽에서 오른쪽으로 피벗의 값보다 큰 데이터가 있는 index 찾기
- pl 인덱스에 들어있는 데이터가 피벗보다 커지면 pl++ 이 실행되지 않고 false가 되어, while문을 빠져나온다.
while (a[pr] > pivot) pr--;
- 피벗기준 오른쪽에서 왼쪽으로 이동하며 피벗의 값보다 작은 데이터가 있는 index 찾기
- pr 인덱스에 들어있는 데이터가 피벗보다 작으면 pr-- 이 실행되지 않고 false가 되어, while문을 빠져나온다.
if (pl <= pr) swap(a, pl++, pr--); (재귀적함수이용)
- pl의 위치값과, pr위치의 값을 교환한다. 현재 pl의 값은 pivot보다 크고, pr의 값은 pivot보다 작기 때문에 교환을 하게 되면 pivot보다 큰 값은 오른쪽으로, pivot보다 작은 값은 왼쪽으로 이동한다.
- 교환한 다음에 다시 돌아와서 p1++, pr--을 해준다. 다음 정렬을 하기 위해서
while (pl <= pr);
- pl이 계속해서 ++되고, pr이 계속해서 --가 되면서 pl이 pr보다 커지면 while문의 조건이 false가 되면서 종료된다.
if(left<pr) myQuick(a,left,pr);
- 요소가 두 개 이상 있을 때 성립함(왼쪽에 있는 조건이 하나만 있다면 실행되지 않음)
- 정렬 후 pivot을 기준으로 왼쪽(pivot보다 작은 값들)을 재정렬할 재귀호출
- 왼쪽 정렬이어서 left가 기준이 되어 새로운 오른쪽 기준이 되는 pr과 둘의 pivot이 새로 생기면서 정렬이 됨
if(pl<right) myQuick(a,pl,right);
- 요소가 두 개 이상 있을 때 성립함(오른쪽에 있는 조건이 하나만 있다면 실행되지 않음)
- 정렬 후 pivot을 기준으로 오른쪽(pivot보다 큰 값들)을 재정렬할 재귀호출
- 오른쪽 정렬이어서 right가 기준이 되어 새로운 왼쪽기준이 되는 pl과 둘의 pivot이 새로 생기면서 정렬이 됨
예제) 퀵정렬을 내림차순으로 하는 프로그램
package al03_sort;
import java.util.Arrays;
import java.util.Scanner;
public class QuickSort2 {
public static void swap(int a[], int idx1, int idx2) {
int tmp = a[idx1]; // 무엇을 먼저 하든 순서는 상관없음
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 시작 인덱스 + 끝인덱스 / 2 => 피벗
public static void myQuick(int[] a, int left, int right) {
int pl = left;
int pr = right;
int pivot = a[(left + right) / 2];
do {
while (a[pl] > pivot)
pl++;
while (a[pr] < pivot)
pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
System.out.println("정렬 후: " + Arrays.toString(a));
if(left<pr)
myQuick(a,left,pr);
if(pl<right)
myQuick(a,pl,right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("배열 수 입력: ");
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<arr.length; i++) {
System.out.print("배열의 값을 입력하세요: ");
arr[i] = sc.nextInt();
}
System.out.println("정렬 전 배열의 값: " + Arrays.toString(arr));
myQuick(arr,0,arr.length-1);
}
}
배열 수 입력: 6
배열의 값을 입력하세요: 79
배열의 값을 입력하세요: 85
배열의 값을 입력하세요: 97
배열의 값을 입력하세요: 88
배열의 값을 입력하세요: 56
배열의 값을 입력하세요: 68
정렬 전 배열의 값: [79, 85, 97, 88, 56, 68]
정렬 후: [97, 85, 79, 88, 56, 68]
정렬 후: [97, 88, 79, 85, 56, 68]
정렬 후: [97, 88, 85, 79, 56, 68]
정렬 후: [97, 88, 85, 79, 68, 56]
정렬 후: [97, 88, 85, 79, 68, 56]
내림차순으로 하기 위해서는
while (a[pl] > pivot) pl++;
while (a[pr] < pivot) pr--;
-> 화살표 방향만 바꾸면 된다.
5. 정렬 알고리즘 비교하기
- 대부분의 프로그래밍 언어에서 지원하는 표준정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.
<문제> 두 배열의 원소 교체>
- 두 개의 배열 A와 B가 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.
- 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.
- 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최대값을 출력하는 프로그램 작성
핵심 아이디어: 매번 A에서 가장 작은 원소를 골라서, B에서 가장 큰 원소와 교체
1) A를 오름차순 정렬, 2) B를 내림차순 정렬
2) 두 배열의 원소를 첫 번째 인덱스부터 차례로 확인하면서 A의 원소가 B의 원소보다 작을 때만 교체 수행
- 이 문제에서 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 O(NlogN)을 보장하는 정렬 알고리즘 이용해야 한다.
import java.io.*;
import java.util.*;
public class Main2775 {
public static void swap(Integer[]a, Integer[]b, int i) {
int tmp = a[i]; // 두 원소를 교체
a[i] = b[i];
b[i] = tmp;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N과 K를 입력받기
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 배열 A의 모든 원소를 입력받기
Integer[] a = new Integer[n];
for(int i=0;i<n;i++) {
System.out.print("배열 A의 원소: ");
a[i] = Integer.parseInt(br.readLine());
}
// 배열 B의 모든 원소를 입력받기
Integer[] b = new Integer[n];
for(int i=0;i<n;i++) {
System.out.print("배열 B의 원소: ");
b[i] = Integer.parseInt(br.readLine());
}
// 배열 A는 오름차순 정렬, 배열 B는 내림차순 정렬
Arrays.sort(a);
Arrays.sort(b, Collections.reverseOrder());
// 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for(int i=0; i<k; i++) {
if(a[i]<b[i]) { // A의 원소가 B의 원소보다 작은 경우
swap(a,b,i);
}else break; // A의 원소가 B의 원소보다 크거나 같을 때 반복무 탈출
}
// 배열 A의 모든 원소의 합을 출력
for(int i=0; i<n; i++) {
System.out.print(a[i] + " ");
}
}
}
'멀티캠퍼스 풀스택 과정 > 알고리즘' 카테고리의 다른 글
| 소수판별 알고리즘 (0) | 2022.01.28 |
|---|---|
| 알고리즘2-1. 선형리스트(LinkedList 연결리스트) (0) | 2022.01.27 |
| 알고리즘1-5. 재귀알고리즘 (0) | 2022.01.26 |
| 알고리즘1-4. 큐(Queue) (0) | 2022.01.26 |
| 알고리즘1-2. 검색 알고리즘(선형검색, 이진검색) (0) | 2022.01.25 |
