[JAVA] 정렬(Sort) - 퀵정렬(Quick Sort), 계수 정렬(Count Sort)

퀵정렬(Quick Sort)

 

퀵정렬은 삽입정렬, 선택정렬, 버블정렬보다 빠른 알고리즘으로 가장 많이 사용되는 알고리즘 입니다.

 

퀵정렬의 핵심은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것 입니다.

퀵 정렬에서 기준 데이터를 피벗이라고 부릅니다.

피벗은 리스트에서 첫 번째 데이터를 피벗으로 정합니다.

 

피벗을 설정한다음 큰 수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식으로 동작합니다.

퀵 정렬의 시간 복잡도는 O(NLogN)입니다.

퀵 정렬은 전체를 3개의 파트로 나눠서 보는게 편합니다.

 

퀵 정렬의 원리

다음과 같이 초기 데이터가 구성되어있습니다.

 

Ⅰ 파트

 

첫번째 데이터를 피벗으로 설정한후, 왼쪽에서부터 피벗보다 큰 데이터 7,

오른쪽에서부터 피벗보다 작은데이터 4를 선택해 교환해줍니다.

다시 그다음으로 피벗보다 왼쪽에서부터 큰데이터 9와 오른쪽에서부터 작은데이터 2를 교환해줍니다.

다시 그다음으로 교환할 데이터를 찾습니다.

교환할 데이터의 위치가 서로 엇갈린것을 알 수 있습니다.

이 경우에는 작은 데이터와 피벗의 위치를 서로 변경합니다.

 

 

Ⅱ 파트

왼쪽 리스트는 모든데이터가 5보다 작습니다. 왼쪽 리스트에도 피벗을 설정하고 정렬을 진행시킵니다.

 

 

Ⅲ 파트

오른쪽 리스트는 모든 데이터가 5보다 큽니다. 오른쪽에도 피벗을 설정하고 정렬을 진행합니다.

 

 

퀵정렬 구현

import java.util.Scanner;

public class QuickSort {
	
	public static void quickSort(int[]arr, int start, int end) {
		if(start>=end) {return;} //원소가 1개일 경우 종료
		int pivot = start; //피벗은 리스트의 첫번째 요소
		int left = start+1;
		int right=end;
		while(left<=right) {
			while(left<=end&&arr[left]<=arr[pivot]) {
				left++; //피벗보다 큰 데이터를 찾을 때까지 반복
			}
			while(right>start&&arr[right]>=arr[pivot]) {
				right--; //피벗보다 작은 데이터를 찾을 때 까지 반복
			}
			
			if(left>right) {//데이터가 엇갈린다면
				int temp = arr[pivot];
				arr[pivot] = arr[right];
				arr[right] = temp;
			}else {
				int temp = arr[left];
				arr[left]= arr[right];
				arr[right]=temp;
			}
			
			
		}
		quickSort(arr, start, right-1); //분할이후 왼쪽에서 정렬수행
		quickSort(arr, right+1,end);
	}
	
	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 + "] : ");
			arr[i] = sc.nextInt();
		}

		quickSort(arr,0,arr.length-1);

		System.out.println("오름차순으로 정렬 했습니다.");
		for (int i = 0; i < arr.length; i++) {
			System.out.println("arr[" + i + "] : " + arr[i]);
		}
	}
}

 

퀵 정렬은 재귀함수를 사용합니다. 

 

 

 

계수 정렬(COUNT SORT)

계수 정렬알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 입니다.

특정한 조건이란 데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때 입니다.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 입니다.

 

계수정렬은 직접 데이터의 값을 비교한 후에 위치를 변경하며 정렬하는 방식이 아닙니다.

일반적으로 별도의 리스트를 선언하고 인덱스를 이용해 정렬에 대한 정보를 담는다는 특징이 있습니다.

 

가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성합니다.

그 다음으로 데이터의 수를 리스트의 인덱스에 담습니다.

리스트의 인덱스는 데이터의 값이며, 인덱스의 값은 해당 데이터의 값입니다.

 

 

계수 정렬 원리

초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 

데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시키면 계수 정렬이 완료됩니다.

 

결과저그로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록됩니다.

리스트의 첫 번째 데이터부터 하나씩 그값만큼 인덱스를 출력하면 됩니다.

 

출력결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

 

계수 정렬 구현

import java.util.Scanner;

public class CountSort {
	public static int[] count;

	public static void countSort(int[] arr) {
		count = new int[arr.length];
		for (int i = 0; i < count.length; i++) {
			count[arr[i]]++;  ///arr[i] 값의 count를 1증가 시킨다
		}
	}

	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 + "] : ");
			arr[i] = sc.nextInt();
		}

		countSort(arr);

		System.out.println("오름차순으로 정렬 했습니다.");
		for (int i = 0; i < count.length; i++) {
			for (int j = 0; j < count[i]; j++) {
				System.out.print(i+" ");
			}

		}

	}
}

 

---

이상으로 퀵정렬과 계수정렬에 대해 알아보았습니다.