코딩테스트(정렬)

쓰게 된 계기

코딩테스트 준비를 하며 정렬을 처음볼땐 이해를 하지만 계속 안보면 잊어버릴 때가 많다. 따라서 각각의 정렬이 어떻게 작동되는지에 대한 설명과 함께 코드를 작성할 생각이다.

버블정렬

데이터를 바꾸는 과정이 자주있는 편이라 마치 그 과정이 버블(?)같은 느낌이라 작명했다는 썰이 있다.

private void bubbleSort() {
        arr = new int[]{5,7,9,0,3,1,6,2,4,8};
        int len=arr.length;
        for(int i=0;i<len;i++) {
            for(int j=0;j<len-i-1;j++) {
            	//현재값이 다음값보다 클 경우 swap
                if(arr[j]>arr[j+1]) {
                    int value = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=value;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

선택정렬

제일 첫번째 인덱스 부터 시작, 초기 인덱스부터 끝까지 데이터를 찾은 후 가장 작은 데이터를 선택 후 초기인덱스와 swap

private void selectionSort() {
        arr = new int[]{5,7,9,0,3,1,6,2,4,8};
        int len = arr.length;
        for(int i=0;i<len;i++) {
            int indexValue = i;
            for(int j=i+1;j<len;j++) {
                if(arr[indexValue]>arr[j]) {
                	// i~len까지 중 인덱스가 가장작은걸 찾는다.
                    indexValue=j;
                }
            }
            // 가장 작은 데이터를 i의 데이터와 바꾼다.
            int value = arr[indexValue];
            arr[indexValue]=arr[i];
            arr[i]=value;
            System.out.println(Arrays.toString(arr));
        }
    }

삽입정렬

인덱스가 전 배열 인덱스 값보다 작을 경우 swap를 한다. 마치 이 과정이 insert를 많이하는 것 같아 작명을 한듯 싶다.

private void insertSort() {
    arr = new int[]{5,7,9,0,3,1,6,2,4,8};
    int len = arr.length;
    for(int i=1;i<len;i++) {
        for(int j=i;j>0;j--) {
        	// j의 데이터 중 전 배열인덱스가 더 크다면
            if(arr[j]<arr[j-1]) {
            	// 전 배열인덱스와 현 배열인덱스의 데이터 변경
                int value = arr[j];
                arr[j]= arr[j-1];
                arr[j-1]=value;
            } else {
            	// 작은거만 있다면 break처리 
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

퀵정렬

피벗을 지정하고 해당 피벗을 기준으로 작은값 큰값을 피벗의 왼쪽 오른쪽에 둔다. 이후 피벗을 제외한 나머지에 해당 로직을 실행시킨다.
다만 정렬이 되있는 것을 퀵정렬 할 경우 최악인 O(N^2)의 시간복잡도를 가진다.

	arr = new int[]{5,7,9,0,3,1,6,2,4,8};
    quickSort(0,arr.length-1);
    private void quickSort(int start, int end) {
    	// 비교대상이 1개만 존재할 경우 리턴
        if(start>=end) return;
        // 피벗(보통 인덱스(0)을 기점)을 설정한다.
        int pivot = start;
        // lt와 rt를 통해 lt는 피벗+1 rt는 제일 끝 배열 인덱스를 둔다.
        int left = start+1;
        int right = end;
        while (left<=right) {
        	// lt는 배열 데이터가 피벗보다 큰 것을 찾는다.
            while (left<=end && arr[left]<=arr[pivot]) left++;
            // rt는 배열 데이터가 피벗보다 작은 것을 찾는다.
            while (right>start && arr[right]>=arr[pivot]) right--;
            if(left>right) {
            // lt보다 rt가 작아지면 그 즉시 rt의 정보와 피벗정보를 바꿈
                int value = arr[pivot];
                arr[pivot]=arr[right];
                arr[right]=value;
                break;
            } else {
            	// lt와 rt가 찾아진 경우 둘을 바꾼다.
                int value = arr[left];
                arr[left]=arr[right];
                arr[right]=value;
            }
            System.out.println(Arrays.toString(arr));
            System.out.println(left+" "+right);
        }
        // 재귀는 (start, rt-1), (rt+1, end)로 파라미터를 두고 진행한다.
        quickSort(start, right-1);
        quickSort(right+1, end);
    }

병합정렬

오랜만에 공부하니까 상당히 오래걸렸다.. 분할정복 기법을 쓰며 분할을 한 뒤 합칠때는 left, right 투포인터를 활용해 작은거를 넣는식으로 진행한다. 사실 잘 이해가 안가서 유투브의 영상을 참고해서 이해했다.
해당 정렬은 최악의 경우도 O(NlogN)이다.

public static void mergeSort(int start, int end) {
	// start가 end보다 크거나 같다면 리턴(배열이 하나이기 때문)
    if(start>=end) return;
    // 중간값
    int mid = (start+end)/2;
    // 중간값까지 분할
    mergeSort(start,mid);
    // 중간값부터 end까지 분할
    mergeSort(mid+1,end);
    // 왼쪽인덱스 포인터
    int left = start;
    // 삽입에 필요한 인덱스
    int index = start;
    // 오른쪽인덱스 포인터
    int right = mid+1;
    // 시작과 끝까지 루프를 통해 tmp에 원본데이터복사
    for(int i=start;i<=end;i++) {
        tmp[i]=arr[i];
    }
    // left나 right 둘중 하나라도 틀릴 때 while루프 종료
    while (left<=mid && right<=end) {
    	// left의 값이 right보다 작을 경우 left를 원본에 삽입
        if(tmp[left]<=tmp[right]) {
            arr[index++]=tmp[left++];
        } else {
        // right의 값이 left보다 작을 경우 left를 원본에 삽입
            arr[index++]=tmp[right++];
        }
    }
    // left가 mid까지 도달못한채로 끝날 경우 해당 for문을 통해 원본에 데이터 삽입
    for(int i=0;i<=mid-left;i++) {
        arr[index+i]=tmp[left+i];
    }
    // right를 하지 않는 이유는 이미 tmp는 원본데이터를 
    //복사해놓은 형태이기 때문에 해당 데이터를 넣어도 원본과 동일하다.
}

계수정렬

최대값을 찾고 최대값이 인덱스로 들어가게 카운팅 배열을 생성한다. 이후 배열의 데이터 값이 존재하면 카운팅 배열을 +1로 카운팅 처리한다. 지금까지 한 정렬 중 가장 빠른 O(N+K(최대값))이다. 다만 메모리는 배열 크기가 있어
O(N+K(최대값))이다.

private void countingSort() {
    arr = new int[]{5,1,2,3,8,4,2,5,7,9,0,3,1,6,2,4,8};
    int max = 0;
    // 최대값 확인
    for(int i=0;i<arr.length;i++) {
        max = Math.max(max,arr[i]);
    }
    // 최대값을 인덱스로 담을 수 있는 배열 생성
    int[] isSelected = new int[max+1];
    // 데이터와 매칭되는 배열인덱스를 하나씩 카운팅
    for(int i=0;i<arr.length;i++) {
        isSelected[arr[i]]++;
    }
    System.out.println(Arrays.toString(isSelected));
    // 데이터가 0이 될떄까지 출력
    for(int i=0;i<isSelected.length;i++) {
        while (isSelected[i]!=0) {
            isSelected[i]--;
            System.out.print(i+" ");
        }
    }
}