정렬기법 (선택/버블/삽입/퀵/병합/힙 )

 정렬(Sorting)이란 데이터 집합을 일정한 순서대로 정렬하는 작업을 말하는데, 알고리즘 구현에 있어서 데이터 집합이 정렬되어있어야 빠른 검색이 가능한것은 당연하다. 정렬 방식에 따라서 안정성과 비용의 차이가 있기 때문에 적절한 방식으로 정렬을 수행할 필요가 있다. 정렬의 기본은 교환, 선택, 삽입이고 여기에 정리할 정렬 알고리즘들도 앞에 세 가지 요소를 응용한 것이라 할 수 있다.

 

 

선택 정렬

 

선택 정렬은 데이터 집합 중에서 가장 작은 값부터 차례로 선택해 적합한 자리에 요소와 교환하는 방식을 반복하는 기법이다. 과정을 보면

 

 1. 데이터 집합 중 가장 작은 값을 찾는다.

 2. 첫번째 요소와 가장 작은 값의 요소를 교환다.

 3. 1-2 를 반복하면서 차례로 두번째로 작은 값과 두번째요소, 세번째로 작은 값과 세번째요소와 같이 진행한다.

 

과정이 단순하고 (n^2 -n)/2 의 복잡도를 갖는데 동일값이 있을 경우 안정적이지 않은 문제점이 있다.

동일한 가중치를 갖는 값의 순서가 정렬 이전과 달라질수 있는 경우를 안정적이지 않다고 하는데, 서로 멀리 떨어져있는 요소를 교환하는 알고리즘의 경우 이와같이 안정적이지 않을 수 있다.

 

 

예시 코드

public class SelectionSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	static void selectionSort(int[] a, int n) {
		for(int i=0; i<n; i++) {
			int min = i;
			for(int j=i+1;j<n; j++) {
				if(a[j]<a[min]) {
					min = j;
				}
			}//for selection pass
			swap(a,i,min);
		}// for
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
	}

}

 

 

버블 정렬

 

버블 정렬의 기본은 인접요소 두 개를 비교해서 원하는 순서와 다르다면 교환하는 기법이다. 버블 정렬의 실행 순서를 아래에 정리해 보면

 

 1. 젤 끝(앞)에 있는 요소를 시작으로 인접 요소와 비교-교환을 하며 젤 앞(뒤) 요소까지 진행한다.

 2. 1. 과정을 다시 수행하는데, 이번엔 젤 앞(뒤)에 요소는 제외한다.

 3. 1-2 과정을 반복할때마다 앞(뒤)의 요소가 하나씩 제외되도록 반복한다. 모든 요소가 제외되고나면 정렬이 끝난다.

 

오름 차순으로 예를 들어보면, 데이터 집합 중에 젤 작은 값은 1-2 과정을 한번 끝내면 젤 앞에 오게된다.

다시 한번 1-2 과정을 실행하면 두 번째로 작은 요소가 데이터 집합 중 두 번째에 위치한다.

버블 정렬은 안정적인 알고리즘이지만 요소의 갯수가 n일때 n(n-1)/2 의 복잡도를 갖는다.

 

예시 코드

import java.util.Scanner;

public class BubbleSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	static void bubbleSort(int[] a, int n) {
		for(int i=0; i<n-1; i++) {
			for(int j=n-1; j>i; j--) {
				if(a[j]<a[j-1]) {
					swap(a,j,j-1);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		
		System.out.println("버블정렬 1.");
		System.out.print("요소수 : ");
		int n = Integer.parseInt(sc.nextLine());
		int[] x = new int[n];
		
		for(int i=0; i<n; i++) {
			System.out.print("arr["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		bubbleSort(x, n);
		
		System.out.println("오름차순 버블 정렬 완료.");
		for(int i=0; i<n; i++) {
			System.out.println("x["+i+"] : "+x[i]);
		}
		
		sc.close();
	}

}

 

 

삽입 정렬

 

삽입 정렬은 요소를 하나씩 선택해서 정렬된 부분 중에 알맞는 위치에 삽입하는 작업을 반복해서 정렬한다. 이 과정을 보면 매번 요소를 선택해서 삽입할 때마다 데이터 집합의 순서가 갱신되는 방식. 과정을 정리해보면

 

 1. 젤 앞(뒤) 요소부터 시작해 요소 하나를 선택하고, 자신보다 앞에 있는 요소들 중 들어갈 자리를 찾아서 삽입한다.

 2. 1. 를 데이터 집합의 끝(앞)까지 반복한다.

 

 1-2 과정을 반복하는 것으로 정렬이 끝나게 되는데 원리는 간단하지만 삽입과정이 실제 구현에서 많은 비용이 소모된다. 왜냐하면 삽입을 위해서는 '현재 선택된 요소 - 들어가야할 자리' 사이에 있는 모든 요소들을 한칸씩 뒤로 배치해야 하기 때문이다. 만약 자료구조가 LinkedList와 같이 삽입비용이 적다면 모르지만, 배열과 같은 구조라면 결국 요소들을 일일이 한 칸 뒤로 배치하는 작업을 반복되야 하기 때문이다. 때문에 삽입 정렬은 요소의 갯수가 n개일때, 최대 n^2의 복잡도를 갖게 된다.

 

예시 코드

import java.util.Scanner;

public class InsertionSort {
	static void insertionSort(int[] a, int n) {
		for(int i=1; i<n; i++) {
			int j;
			int temp = a[i];
			for(j=i;j>0&&a[j-1]>temp;j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("단순 삽입 정렬");
		System.out.print("요소수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		insertionSort(x,num);
		
		System.out.println("정렬 완료");
		for(int i = 0; i<num; i++) {
			System.out.println("x["+i+"] : " + x[i]);
		}
		
		sc.close();
		
	}

}

 

 

퀵 정렬

 

이름 대로 빠른 정렬인데 자료들을 반으로 나눠가며 정렬을 반복하는 방식. 여기서 자료를 나누는 기준을 피벗(pivot)이라 부른다. 나뉘어진 자료의 그룹이 한 개의 요소만 갖게 되면 정렬이 종료된다. 오름차순 퀵 정렬의 순서를 보면

 

 1. 피벗을 정하고 그룹의 양 끝 요소부터 하나씩 전진하며 피벗과 값을 비교한다.

 2. 앞쪽부터 진행하던 요소가 피벗보다 값이 크다면 정지한다.

 3. 뒤쪽부터 진행하던 요소가 피벗보다 값이 작다면 정지한다.

 4. 앞쪽에서 선택중인 요소가 뒤쪽에서 선택중인 요소보다 크다면 두 값을 교환하고 1-3을 다시 반복한다.

 5. 앞쪽에서 선택중인 요소가 뒤쪽에서 선택중인 요소보다 작다면 1-3반복을 멈추고 피벗을 기준으로 그룹을 두개로 나누어 1-4를 반복한다.

 6. 그룹의 요소가 한 개만 남으면 정렬을 종료한다.

 

위에 작업 순서를 보면 복잡해 보일지 모르지만 이를 표로 보면 한눈에 들어온다. 쉽게 다시 설명하면 기준을 정해서 기준보다 큰그룹, 작은그룹을 나누고 각 그룹으로 다시 기준을 잡고 그룹나누기를 반복하는 기법. 복잡도는 평균 n log n의 복잡도를 갖기에 상술한 버블 정렬, 삽입 정렬보다 빠르지만 데이터의 분포에 따라 최대 n^2의 복잡도를 갖게 된다.

 

예시 코드

 

import java.util.Scanner;

public class QuickSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	static void quickSort(int[] a, int left, int right) {
		int pl = left;
		int pr = right;
		int x= a[(pr+pl)/2];
		
		System.out.printf("x[%d]~x[%d] : {",left,right);
		for(int i = left; i<right; i++) {
			System.out.printf("%d, ",a[i]);
		}
		System.out.printf("%d}\n",a[right]);
		
		
		do {
			while(x>a[pl]) pl++;
			while(x<a[pr]) pr--;
			if(pl<=pr) {
				swap(a, pl++, pr--);
			}
		} while(pl<=pr);
		
		if(left<pr) quickSort(a,left, pr);
		if(right>pl) quickSort(a,pl,right);
		
			
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요소수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		quickSort(x, 0, num-1);
		
		System.out.println("퀵정렬 수행");
		for(int i =0; i<num; i++) {
			System.out.print(x[i]+" ");
		}
		
		sc.close();
	}

}

 

 

병합 정렬

 

 병합 정렬은 배열을 나누어 각각 정렬한 다음 병합하는 작업을 반복하는 방식의 정렬. 병합 정렬의 전체 과정을 보기전에 정렬되어 있는 두 그룹의 데이터 집합을 병합하며 정렬하는 과정을 알아야 한다. 그 과정을 아래에서 보면

 

 1. 나뉘어진 두 그룹이 정렬이 되었다는 가정(혹은 요소가 1개)하에 각 그룹의 젤 앞에 요소부터 차례로 값을 읽는다.

 2. 두 그룹에서 현재 읽은 값이 더 작은 순서대로 새로운 그룹에 넣는다. 두 그룹의 모든 요소가 새로운 그룹에 들어가면 병합 정렬이 종료된다.

 

 정렬된 두 그룹을 병합정렬하는 과정이 위와 같음을 이해하고 병합 정렬의 전체 과정을 아래에서 보자

 

 1. 데이터 집합을 둘로 나눈다. 나누어진 그룹의 요소가 2개 이상이면 다시 그룹을 둘로 나누기를 반복한다.

 2. 요소가 1개인 그룹이 되면 상술한 정렬된 두 그룹간 병합 정렬을 하면서 나뉘어졌던 모든 그룹들을 병합 정렬로 거슬러 올라간다.

 3. 2.를 반복하여 나뉘어졌던 모든 그룹이 하나의 데이터 집합으로 병합 정렬된다.

 

병합 정렬은 안정한 정렬기법에 복잡도가 n log n을 보장하는데 단점으로는 위의 과정에서 새로운 그룹이 계속해서 생겨나기 때문에 별도의 메모리 공간이 필요하다.

 

예제 코드

import java.util.Scanner;

public class MergeSort {
	static int[] buff;
	
	static void __mergeSort(int[] a, int left, int right) {
		if(left<right) {
			int i;
			int j = 0;
			int p = 0;
			int k = left;
			int center = (left+right)/2;
			__mergeSort(a,left, center);
			__mergeSort(a,center+1, right);
			
			for(i=left; i<=center; i++) {
				buff[p++] = a[i];
			}
			
			while(i<=right&&j<p) {
				a[k++] = (buff[j]<a[i])? buff[j++] : a[i++];
			}
			
			while(j<p) a[k++] = buff[j++];
			
			
		}
	}
	
	static void mergeSort(int[] a, int n) {
		buff = new int[n];
		__mergeSort(a, 0, n-1);
		buff = null;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("병합정렬");
		System.out.print("요솟수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i =0; i<num; i++) {
			System.out.print("x["+i+"] :");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		mergeSort(x, num);
		
		System.out.println("정렬 완료");
		for(int i =0; i<num; i++) {
			System.out.println("x["+i+"] : "+x[i]);
			
		}
		
		sc.close();
	}

}

 

힙 정렬

 

 힙정렬은 선택 정렬을 힙과 함께 사용해 정렬하는 알고리즘이다. 힙은 부모의 값이 자식의 값보단 큰 완전이진트리를 말한다.(반대로 늘 자식이 더 크더라도 규칙성이 유지되면 힙이라 한다.) 힙의 특성에 따라 완전이진트리의 루트가 늘 최대값이므로, 루트를 꺼내고 남은 값들을 다시 힙으로 구성하는 작업을 반복하므로서 데이터집합을 정렬할 수 있다.

 과정을 보자면

 

 1. 데이터 집합을 힙으로 구성한다.

 2. 루트값을 꺼내고, 마지막 요소를 루트로 보낸다.

 3. 남은 데이터들을 다시 힙이 되도록 한다.

 4. 2-3 작업을 반복하면서 꺼낸 루트값들을 나열하면 힙 정렬이 완료된다.

 

 위 과정들을 배열로 구현해 보면

 1. 배열을 힙구조로 정렬하고

 2. 루트가 되는 인덱스 0의 요소를 꺼내서 배열의 젤 뒤 요소와 교환한다.

 3. 젤 뒤요소를 제외하고 나머지 요소들로 다시 힙을 만든다.

 4. 2-3을 반복할때마다 뒤의 요소를 하나씩 추가로 제외하면서 실행하면 배열이 오름차순으로 정렬된다.

 

힙정렬은 정렬 자체는 선택정렬과 동일하기 때문에 매우 간단한데 힙에 대한 이해와 힙을 구현할줄 알아야 한다. 시간복잡도는 선택정렬이 n^2 인데 반해 힙 정렬은 n log n의 복잡도를 갖는다.

 

예시 코드

import java.util.Scanner;

public class HeapSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	static void downHeap(int[] a, int left, int right) {
		int t = a[left];
		int child;
		int parent;
		
		for(parent = left;parent<(right+1)/2; parent=child) {
			int cl = parent*2+1;
			int cr = cl+1;
			child = (cr<=right&&a[cr]>a[cl])?cr:cl;
			if(t >=a[child]) break;
			
			a[parent] = a[child];
		}
		a[parent] = t;
	}
	
	static void heapSort(int[] a, int n) {
		for(int i=(n-1)/2; i>=0; i--) {
			System.out.println(i);
			downHeap(a, i, n-1);
		}
		
		for(int i=n-1;i>0; i--) {
			swap(a,0,i);
			downHeap(a,0,i-1);
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("힙 정렬");
		System.out.println("요솟수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		heapSort(x,num);
		
		System.out.println("오름차순 힙정렬 완료");
		for(int i =0; i<num; i++) {
			System.out.println("x["+i+"] : "+x[i]);
		}
		
		sc.close();
	}

}