[LeetCode] Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

 

Example 1:Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1] Output: [0,1,2]

Example 3:

Input: nums = [0] Output: [0]

Example 4:

Input: nums = [1] Output: [1]

 

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is 0, 1, or 2.

Follow up:

• Could you solve this problem without using the library's sort function?
• Could you come up with a one-pass algorithm using only O(1) constant space?

빨강, 흰색 또는 파랑 색의 n 개의 객체가있는 배열 번호가 주어지면

동일한 색상의 객체가 빨강, 흰색 및 파랑 순서의 색상으로 인접하도록 제자리에 정렬합니다.

정수 0, 1, 2를 사용하여 각각 빨간색, 흰색, 파란색을 나타냅니다.

 

라이브러리 사용없이 구현

O (1) 상수 공간만을 사용하는 원 패스 알고리즘을 생각해 낼 수 있습니까?

In-place (제자리 정렬) - 추가적인 배열을 생성하지 않고 지역변수의 활용 정도만 하는 정렬

 

제자리 정렬의 종류들

• Insertion Sort
• Selection Sort
• Bubble Sort
• Shell Sort
• Heap Sort
• Quick Sort(정렬 알고리즘-4.2: 정의에 따라서 Not in place sorting으로 볼 수도 있으나 흔히 In-place로 본다.)

등등

 

일단 만들기 쉬운 버블소트

시간 : O(N^2)

공간 : O(N)

class Solution {
	    public void sortColors(int[] nums) {
	        int temp;
	    	for(int i = 0; i < nums.length; i++)
	    	{
	    		for(int j = 0; j < nums.length -i -1; j++)
	    		{
	    			if(nums[j+1] < nums[j])
	    			{
	    				temp = nums[j];
	    				nums[j] = nums[j+1];
	    				nums[j+1] = temp;
	    			}
	    		}
	    	}
	    }
	}
    
    bubble sort O(n^2)
    최악 300 * 300 90000이면 금방 끝나는편이다.
    Runtime: 2 ms
    Memory Usage: 37.8 MB

 

이미 수의 범위가 정해져있다면 계수 정렬이 효율적이지 않을까?

N -> 데이터 개수 , 데이터 최대값 -> K

계수정렬의 최악의 수행시간 - O(N+K)

class Solution {
	    public void sortColors(int[] nums) {
	    	final int MAX_VALUE = 2;
	    	int temp;
            	int idx = 0;
	    	int[] cnt = new int[MAX_VALUE + 1];
	    	
	    	for (int i = 0; i < nums.length; i++) {
	            cnt[nums[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
	        }
	        for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
	            for (int j = 0; j < cnt[i]; j++) {
                    nums[idx++] = i;
	            }
	        }
	    }
	}

 

quickSort

O(nlogn) /

O(N^2) 정렬 되어있을 수록 느림

class Solution {
    public void sortColors(int[] nums) {

        Solution solution = new Solution();
        solution.quickSort(nums, 0, nums.length - 1);
    }
    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);
    }
}
// 동빈나님 깃허브에 있는 퀵소트 예제

 

참고 서적

이것이 취업을 위한 코딩테스트다 with python (저자 동빈나님)

 

참고 블로그

devjin-blog.com/sort-algorithm-1/

💻 Stable Sort, inplace algorithm이란? 왜 중요한가?

starkying.tistory.com/entry/Bubble-Sort-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-Selection-Sort-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC

Bubble Sort (버블 정렬) / Selection Sort (선택 정렬)