[알고리즘] 기본 정렬 (버블정렬, 선택정렬, 삽입정렬)

0) 정렬이란?

정렬이란 데이터를 정해진 순서대로 나열하는 것이다.

1) 버블정렬

두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꿔주는 정렬 알고리즘이다.

 

예시)

6 5 3 1

1- array[0]와 array[1] 비교 : 6, 5
array : [5, 6, 3, 1]
2- array[1]과 array[2] 비교 : 6, 3
array : [5, 3, 6, 1]
3- array[2]와 array[3] 비교 : 6, 1
array : [5, 3, 1, 6]      -> 1번 턴 종료. 가장 큰 수가 맨 뒤로 이동함.
4- array[0]과 array[1] 비교 : 5, 3
array : [3, 5, 1, 6]
5- array[1]과 array[2] 비교 : 5, 1
array : [3, 1, 5, 6]      -> 2번 턴 종료. 
6- array[0]과 array[3] 비교 : 3, 1
array : [1, 3, 5, 6]      -> 3번 턴 종료. 정렬 끝

 

자바 구현 코드

package Soting;

public class BubbleSort {
	
	public static void swap(int[] array, int index1, int index2) {
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public static void bubblesort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) { 
			boolean isSwap = false;  
			for (int j = 0; j < array.length - i - 1; j++) {
				if (array[j] > array[j + 1]) {
					swap(array, j, j+1);
					isSwap = true; 
				}
			}
			if (!isSwap) { // 만약, swap된게 없다면 순서대로 정렬이 된 것이므로 비교 종료
				break;
			}
		}
	}

	public static void main(String[] args) {
		int[] array = new int[5];
		
		for (int i = 0; i < 5; i++) {
			array[i] = (int) (Math.random() * 10);
		}
		for (int num : array)
			System.out.print(num + " ");
		System.out.println();
		bubblesort(array);
		for (int num : array)
			System.out.print(num + " ");
	}
}

 

*버블 정렬의 시간복잡도

반복문이 2개이므로 O(n^2)이다.

완전 정렬이 되어 있는 상태라면, 배열 전체를 1회만 비교하면 되므로 O(n)이 최선의 시간복잡도가 된다.

2) 선택정렬

선택정렬이란 1. 주어진 데이터 중 최소값을 찾아서 데이터 맨 앞과 교체한다. 2. 맨 앞 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

예시)
데이터가 2개 일때
 array = [5, 2]
 처음 실행 : [2, 5]
데이터가 3개 일때
 array = [5, 1, 3]
 처음 실행 : 최소값이 1이므로 맨앞 데이터와 교체함. -> [1, 5, 3]  
 두번째 실행 : 맨앞 데이터를 제외하고 데이터 중 최소값(3)과 맨 앞을 교체함 -> [1, 3, 5]
데이터가 4개 일때
array = [6, 4, 2, 1]
 처음 실행 : [1, 4, 2, 6] 
 두번째 실행 : [1, 2, 4, 6]
 세번째 실행 : 변화없음

자바 선택정렬 구현 코드

package Soting;

public class SelectSort {
	
	public static void selectsort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[minIndex] > array[j]) {
					minIndex = j;
				}
			}
			swap(array, i, minIndex);
		}
	}
	
	public static void swap(int[] array, int index1, int index2) {
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public static void main(String[] args) {
		int[] array = new int[5];
		
		for (int i = 0; i < 5; i++) {
			array[i] = (int) (Math.random() * 100);
		}
		for (int num : array)
			System.out.print(num + " ");
		System.out.println();
		selectsort(array);
		for (int num : array)
			System.out.print(num + " ");
	}
}

*선택정렬 시간복잡도

반복문이 2개이므로 O(n^2)이다.

 

3) 삽입정렬

두 번째 인덱스의 데이터를 기준으로 처음 시작하는데, 앞에 있는 데이터와 비교해서 key값이 더 작으면 B값을 뒤 인덱스로 복사하고 key보다 더 큰 데이터를 만날때 까지 반복하고 큰데이터를 만나면 그 바로 뒤에 key를 이동하는 정렬 알고리즘입니다.

 

기준인덱스	비교 시작 인덱스	비교 끝 인덱스
1	0	0
2	1	0
3	2	0
4	3	0

삽입정렬 자바 구현 코드

package Soting;

public class InsertSort {
	
	public static void insertsort(int[] array) {
		
		for (int i = 0; i < array.length - 1; i++) { //데이터가 2개일 경우 1번 비교 - 데이터가 3개일 경우 2번 비교
			for (int j = i + 1; j > 0; j--) { // 첫번째 실행 : 기준인덱스는 1임, 두번째 실행: 기준인덱스는 2임
				if (array[j] < array[j - 1]) {
					swap(array, j, j-1);
				} else { // 자신의 바로 앞 데이터 이전은 모두 정렬이 된 상태이므로 바로 앞 데이터가 더 작다면, 그대로 반복문 종료
					break;
				}
			}
		}
	}

	public static void swap(int[] array, int index1, int index2) {
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public static void main(String[] args) {
		int[] array = new int[5];
		
		for (int i = 0; i < 5; i++) {
			array[i] = (int) (Math.random() * 100);
		}
		for (int num : array)
			System.out.print(num + " ");
		System.out.println();
		insertsort(array);
		for (int num : array)
			System.out.print(num + " ");
	}
}

* 삽입정렬 시간복잡도

반복문이 2개므로 O(n^2)

완전 정렬이 되어있는 상태라면 O(n)

 

4) 자바에서의 정렬 사용

*오름차순 정렬

public static void sort(int[] a) : sort() 메소드를 사용하여 자바에서 오름차순으로 배열 정렬을 할 수 있다.

 

*내림차순 정렬

Java Collections 클래스는 사전적순서 반대로 정렬을 하는 reverseOrder() 메소드를 제공한다.

public static <T> Comparator<T> reverseOrder()  

 

package Soting;

import java.util.Arrays;
import java.util.Collections;

public class SortInJava {

	public static void main(String[] args) {
		//오름차순
		int[] array1 = {10, 3, 6, 2, 7};
		Arrays.sort(array1);
		System.out.println(Arrays.toString(array1));
		
		//내림차순
		Integer[] array2 = {10, 3, 6, 2, 7};
		Arrays.sort(array2, Collections.reverseOrder());
		System.out.println(Arrays.toString(array2));
	}

}

 

추가학습

int는 원시형 변수이고, Integer는 클래스타입이다.