정렬 뿌시기

힙정렬, 합병정렬, 퀵정렬

1. 힙 정렬

// maxHeap(data, number) - data : 정렬 대상배열, number : 배열의 크기

// 최대힙 정렬
void maxHeap(int []data, int number){
    
    for(int i=1; i< number; i++){
    // 0을 제외한 이유는 비교대상이 자식 노드이므로 루트노드를 제외하였기 때문이다.
        
    	int child = i; // 루트노드를 제외하곤 항상 어떤 노드의 자식이다.
        while(child > 0){
            // (child-1) / 2는 부모 인덱스를 의미한다.
            // -1을 하기 싫으면 최상단 루트의 인덱스를 1부터한다.(지금은 0)
            int parent = (child - 1) / 2;	
            
            // 부모노드값이 자식보다 작으면 바꾼다.
            if(data[child] > data[parent]){
                int temp = data[parent];
                data[parent] = data[child];
                data[child] = temp;
            }
            
            // 루트노드까지 반복한다.
            child = parent;	
        }
    }
    
}

2. 합병 정렬

int[] arr = {5, 3, 2, 4, 9};
mergeSort(arr, 0, arr.length-1);

void mergeSort(int[] arr, int start, int end){
    if(start < end){
        int middle = (start + end) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle+1, end);
        merge(arr, start, middle, n);
    }
}

void merge(int[] arr, int start, int middle, int end){
    int i = start;
    int j = middle + 1;
    int k = start;
    int temp[] = new int[(end-start)+1]; //합쳐진 결과를 저장하는 임시변수 
    int idx = 0;
    
    // 작은 순서대로 배열에 삽입
    while(i <= middle && j <= end){
        if(arr[i] <= arr[j]){
            temp[idx++] = arr[i++];
        } else {
            temp[idx++] = arr[j++];
        }
    }
    
    // 한쪽 인덱스 범위를 초과 했을때 나머지 한쪽의 값들을 전부 temp 배열에 추가
    if(i > middle){
        // 왼쪽은 전부 정렬된 상태 오른쪽 나머지 temp 배열에 추가
        for(int temp=j; temp <= end; temp++){
            temp[idx++] = arr[temp];
        }
    } else {
        // 오른쪽은 전부 정렬된 상태 왼쪽 나머지 temp 배열에 추가
        for(int temp=i; temp <= middle; temp++){
            temp[idx++] = arr[temp];
        }
    }
    
    for(int val=start; val <= end; val++){
        arr[val] = temp[val-start];
    }
}

3. 퀵정렬

4. 퀵 정렬의 구체적인 개념

int[] list = new int[]{5, 3, 8, 4, 9, 1, 6, 2, 7};
quick_sort(list, 0, list.length-1);

void quick_sort(int[] list, int left, int right){

    // 정렬 범위가 2개 이상의 데이터이면
    if(left < right) {
        // partition 함수를 호출하여 피벗을 기준으로 비균등 분할
        int q = partition(list, left, right); // q : 피벗의 위치
    
    	// 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q-1);
        quick_sort(list, q+1, right);
    }
    
}

int partition(int []list, int left, int right){
    int pivot, temp;
    int low, high;
    
    low = left;
    high = right+1;
    pivot = list[left];
    
    do {
        // list[low]가 피벗보다 작으면 계속 low를 증가
        // low는 left+1에서 시작(left는 피벗)
        // pivot이 list[left]보다 큰 값에서 멈춘다.
        do {
            low++;
        } while(low <= right && list[low] < pivot);
        
        // list[high]가 피벗보다 크면 계속 high를 감소
        // high는 right에서 시작
        // pivot이 list[high]보다 작은 값에서 멈춘다.
        do {
            hight--;
        } while(high >= left && list[high] > pivot);
        
        // low와 high가 교차하지 않았으면 list[low]와 list[high] 교환
        if(low < high){
            swap(list[low], list[high]);
        }
        
    } while (low < high)
        
    swap(list[left], list[high]);
    
    return high;
}

Comments

comments powered by Disqus