[Algorithm] 정렬

BruteForceA·2022년 1월 12일

정렬이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

정렬의 종류

거품 정렬(Bubble Sort)

선택 정렬(Selection Sort)

삽입 정렬(Insertion Sort)

퀵 정렬(Quick Sort)

병합정렬(Merge Sort)

버블 정렬(Bubble Sort)

처음 원소와 바로 옆 원소를 비교하고
현재 원소가 옆 원소보다 크면 원소를 교환하고 옆 원소로 이동해서 해당원소와 다음원소를 비교를 반복한다. 하나씩 정렬이 되고 맨 끝에 큰 숫자가 오면 맨 끝 원소는 가장 큰수니까 비교 할 필요가 없다. 다음 차수에는 -1 을 하여 n-1 까지만 비교한다.

그림출처

예제

버블정렬의 장점

코드구현이 쉽다

코드가 직관적이다.

버블정렬의 단점

비효율적이다. 시간 복잡도가 O(N^2)이기 떄문에 효율적인 정렬방법으로는 사용되지 않는다.

예시코드


public class BubbleSort {

public static void main(String[] args) {
	int[] a = { 35, 3, 6, 1000, 55, 76, 987, 43, 654, 67, 4, 5, 76, 3410, 8, 342, 76 };
	int b;
		
	for (int i = 0; i < a.length; i++) { // 0부터 n차수 까지
		for (int j = 0; j < a.length - i - 1; j++) { // 현재 원소가 값이 더 크면 다음 원소와 자리를 바꾼다.
			if (a[j] > a[j + 1]) {
				b = a[j];
				a[j] = a[j + 1];
				a[j + 1] = b;
				}
			}
		}

		for (int i = 0; i < a.length; i++) {
		System.out.print(a[i]+ " ");
		}
	}

}

결과

선택정렬(Selection Sort)

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로

주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

예시

그림출처

선택정렬의 장점

구현이 쉽고 알고리즘이 단순하다.

원소 교환 횟수가 적어서, 교환이 많이 일어나야하는 배열일때 유리하다.
(내림차순 정렬 되어있는 자료를 오름차순으로 재정렬 할 때)

제자리 정렬 방식이므로 다른 메모리 공간을 필요로 하지 않는다.

선택정렬의 단점

이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬 하게 될때 최악의 처리속도

불안정 정렬이다.

시간복잡도가 O(n^2)이고, 비효율적이다.

예시코드

public class SelectionSort {

public static void selectionSort(int[] list) {
	int indexMin, temp;

	for (int i = 0; i < list.length - 1; i++) {
		indexMin = i; // 첫 원소부터 마지막-1 원소까지 정렬대상.
			// 선택 정렬을 하다보면 마지막 원소는 자동으로 정렬된다.

		for (int j = i + 1; j < list.length; j++) {
			// 정렬 대상 다음 원소부터 마지막 원소까지 정렬 대상보다 작은 값을 찾는다.

			if (list[j] < list[indexMin]) {
				// 작은 값을 찾으면 인덱스를 바꿔준다
				indexMin = j;
				}
			}
		temp = list[indexMin]; // 바뀐 인덱스로 서로 값을 바꿔준다.
		list[indexMin] = list[i];
		list[i] = temp;
		}

		// 첫 원소부터 시작해서 계속 다음으로 넘어가면서 정렬이된다.
	for (int s : list) {
		System.out.print(s + " ");
		}
	}

	public static void main(String[] args) {

		int[] arr = { 6, 1, 4, 10, 16, 7 };
		selectionSort(arr);
	}

}

결과

삽입정렬 (Insertion Sort)

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.

예시

삽입정렬 장점

구현이 쉽다.

선택,버블 정렬같은 시간복잡도 O(n^2)인 정렬에 비해 빠르고 안전하다.

정렬되어있는경우 매우 효율적이다.

알고리즘이 단순함

정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

삽입정렬 단점

평균과 최악의 시간복잡도가 O(n^2)으로 비효율 적이다.

배열의 길이가 길어질수록 비 효율적이다.

예시코드


public class InsertionSort {

public static void main(String[] args) {
		// TODO Auto-generated method stub
	int[] a = { 35, 3, 6, 1000, 55, 76, 987, 43 };
	
    //두 번쨰 원소부터 끝까지
	for(int i=1; i<a.length; i++) {
		int temp=a[i]; 
		int prev=i-1;
        //현재 원소부터 그 이전 원소들중 더 큰 원소가 있으면
		while(prev>=0 && a[prev] >temp) {
        //현재원소보다 이전원소가 더 크면 
        //오른쪽으로 한칸씩 밀어내는것을 반복
			a[prev+1] = a[prev]; 
			prev--;
			}
		a[prev+1]=temp; //임시로 저장해놓은 값을 삽입한다.
        
		}
		
		for(int s : a) { //출력 코드
			System.out.print(s+ " ");
		}

	}

}