본문 바로가기
TechNical/JAVA

[자료구조][JAVA] Sort 모음

by 강멍멍이 2020. 10. 4.
반응형

요즘 멍청이가 된 듯 하여 뜨문뜨문 시작하는 자료구조 시리즈...

버블, 머지, 퀵 소트를 한번에 쭉 찍어 보고 비교를 해 보자.

[ Sort.java ]

package com.kei;

public class Sort {
	
	static int loopCount;
	
	public static void main(String[] args) {
		Sort sort = new Sort();
		
		int sourceArray[] = {5, 7, 2, 3, 8, 4, 1, 6};
		int workArray[];
		
		sort.printArray(sourceArray, true);
		loopCount = 0;
		workArray = sourceArray.clone();
		sort.bubbleSort(workArray);
		System.out.print("Bubble Sort[" + loopCount + "] : ");
		sort.printArray(workArray, true);		
		System.out.println();
		
		sort.printArray(sourceArray, true);
		loopCount = 0;
		workArray = sourceArray.clone();
		int tempArray[] = new int[sourceArray.length];
		sort.mergeSort(workArray, tempArray, 0, workArray.length - 1);
		System.out.print("Merge Sort[" + loopCount + "] : ");
		sort.printArray(workArray, true);
		System.out.println();
		
		sort.printArray(sourceArray, true);
		loopCount = 0;
		workArray = sourceArray.clone();
		sort.quickSort(workArray, 0, workArray.length - 1);
		System.out.print("Quick Sort[" + loopCount + "] : ");
		sort.printArray(workArray, true);
		System.out.println();
	}
	
	
	// Bubble Sort ------------------------------------------------
	// i 와 i + 1 을 비교해서 교환한다.
	private void bubbleSort(int[] getArray) {
		int tempData;
		for(int x = 0 ; x < getArray.length ; x++) {
			loopCount++;
			for(int i = 0 ; i < getArray.length - 1 ; i++) {
				loopCount++;
				if(getArray[i] > getArray[i + 1]) {
					tempData = getArray[i];
					getArray[i] = getArray[i + 1];
					getArray[i + 1] = tempData;
					System.out.print("> "); printArray(getArray, true);
				}
			}
		}
		
	}
	// ------------------------------------------------------------
	
	

	
	// Merge Sort -------------------------------------------------
	// 최소단위로 분할 정렬한 후 다시 병합 정렬한다.
	private void mergeSort(int[] getArray, int[] tempArray, int start, int end) {
		loopCount++;
		if (start < end) {
						
			int mid = (start + end) / 2;
			mergeSort(getArray, tempArray, start, mid);	// 좌측 처리, 최소 단위가 될 때까지 end값에 mid를 넣어서 호출 된다.
			mergeSort(getArray, tempArray, mid + 1, end); // 우측 처리, 최소 단위가 될 때까지 start값에 mid를 넣어서 호출 된다.
			
			int startPoint = start;
			int midPoint = mid + 1;
			int tempIdx = startPoint;
			
			while (startPoint <= mid || midPoint <= end) {
				loopCount++;
				if (midPoint > end || (startPoint <= mid && getArray[startPoint] < getArray[midPoint])){
					tempArray[tempIdx++] = getArray[startPoint++];
				} else {
					tempArray[tempIdx++] = getArray[midPoint++];
				}
			}
			
			for (int i = start ; i <= end ; i++) {
				getArray[i] = tempArray[i];
			}
			
			System.out.print(start + "/" + end + "> "); printArray(getArray, false);
			System.out.print("| "); printArray(tempArray, false);
			System.out.println();
		}
	}
	// ------------------------------------------------------------
	
	
	
	// Quick Sort -------------------------------------------------
	// 피봇값을 지정하고 좌, 우 값과 비교한 후 교환한다.
	private void quickSort(int[] getArray, int left, int right) {
		if(left < right) {
			loopCount++;
			int index = partition(getArray, left, right);
			quickSort(getArray, left, index - 1);
			quickSort(getArray, index + 1, right);
		}
	}	
	
	private int partition(int[] getArray, int left, int right) {
		int midIndex = (left + right) / 2;
		int pivotValue = getArray[midIndex];
		int tempData;
		
		while(left < right) {
			loopCount++;
			while((getArray[left] < pivotValue) && (left < right)) {
				loopCount++;
				left++;
			}
			
			while((getArray[right] > pivotValue) && (left < right)) {
				loopCount++;
				right--;
			}
			
			if(left < right) {
				//System.out.print("> " + pivotValue + "/" + getArray[left] + "(" + left +")/" + getArray[right] + "(" + right + ") : ");
				tempData = getArray[left];
				getArray[left] = getArray[right];
				getArray[right] = tempData;
				
				System.out.print("> "); printArray(getArray, true);
			}
		}
		
		//System.out.println("-------------1 " + pivotValue + " / " + left + " / " + right);
		
		return left;
	}
	// ------------------------------------------------------------
	

	private void printArray(int[] getArray, boolean lf) {
		for(int i : getArray) {
			System.out.print(i + " ");
		}		
		
		if (lf) {
			System.out.println();
		}
	}
	
}

 

실행하면 결과는 아래와 같이 찍힌다.

5 7 2 3 8 4 1 6  

> 5 2 7 3 8 4 1 6 
> 5 2 3 7 8 4 1 6 
> 5 2 3 7 4 8 1 6 
> 5 2 3 7 4 1 8 6 
> 5 2 3 7 4 1 6 8 
> 2 5 3 7 4 1 6 8 
> 2 3 5 7 4 1 6 8 
> 2 3 5 4 7 1 6 8 
> 2 3 5 4 1 7 6 8 
> 2 3 5 4 1 6 7 8 
> 2 3 4 5 1 6 7 8 
> 2 3 4 1 5 6 7 8 
> 2 3 1 4 5 6 7 8 
> 2 1 3 4 5 6 7 8 
> 1 2 3 4 5 6 7 8 
Bubble Sort[64] : 1 2 3 4 5 6 7 8 

5 7 2 3 8 4 1 6 
0/1> 5 7 2 3 8 4 1 6 | 5 7 0 0 0 0 0 0 
2/3> 5 7 2 3 8 4 1 6 | 5 7 2 3 0 0 0 0 
0/3> 2 3 5 7 8 4 1 6 | 2 3 5 7 0 0 0 0 
4/5> 2 3 5 7 4 8 1 6 | 2 3 5 7 4 8 0 0 
6/7> 2 3 5 7 4 8 1 6 | 2 3 5 7 4 8 1 6 
4/7> 2 3 5 7 1 4 6 8 | 2 3 5 7 1 4 6 8 
0/7> 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8 
Merge Sort[39] : 1 2 3 4 5 6 7 8 

5 7 2 3 8 4 1 6 
> 1 7 2 3 8 4 5 6 
> 1 3 2 7 8 4 5 6 
> 1 2 3 7 8 4 5 6 
> 1 2 3 4 8 7 5 6 
> 1 2 3 4 6 7 5 8 
> 1 2 3 4 6 5 7 8 
> 1 2 3 4 5 6 7 8 
Quick Sort[33] : 1 2 3 4 5 6 7 8 

 

각 알고리즘의 시간복잡도를 찍어 봤는데... 카운터 위치가 이게 맞는 건지 모르겠다 -_-

왠지 아닌거 같아서 몹시 부끄러운건 기분 탓...

반응형

댓글