정렬 만들기

Project : SortProject
Pakage : test.sort
Main-class : TestSort

 

<삽입정렬>

import java.util.ArrayList;

public class TestSort {

	private static ArrayList<Integer> data;

	public static void main(String[] args) {
		// 삽입정렬
		data = new ArrayList<Integer>();
		data.add(3); data.add(65); data.add(68); data.add(53); data.add(20);
		data.add(8); data.add(48); data.add(25); data.add(86); data.add(4);
		
		//정렬하기 전 data
		System.out.println(data);
		
		//삽입 정렬 메서드
		insertSort(data, data.size());
		System.out.println("insert Sort :: " + data);
	}

	private static void insertSort(ArrayList<Integer> data2, int size) {
		// 삽입정렬 코드
		int i , j, key = 0;
		
		// 1번 인덱스부터 증가하면서 하나씩 값을 가져옴. (순차적으로 전체 데이터를 가져옴.) 
		// 1번 인덱스인 이유 -> 0번 인덱스는 비교할 대상이 없으므로
		for(i=1; i<data2.size();i++) {
			key = data2.get(i);
			
			// 리스트 i번째의 바로 앞(i-1) 인덱스의 값부터 0번째 인덱스까지 점점 줄어들면서 key와 비교
			for(j= i-1; j>= 0; j--) {
				if(data2.get(j)>key) {
				//set(index, value) -> 해당 인덱스에 값을 교체 
				// key보다 크면 해당 값(data2.get(j))을 i 인덱스의 값과 교체
					data2.set(j+1, data2.get(j));
				}else {
					break;
				}
			}
			data2.set(j+1, key);
		}
	}

}

 

<버블정렬>

 

public class TestSort {

	private static ArrayList<Integer> data;

	public static void main(String[] args) {

		data = new ArrayList<Integer>();
		data.add(3); data.add(65); data.add(68); data.add(53); data.add(20);
		data.add(8); data.add(48); data.add(25); data.add(86); data.add(4);
		
		//정렬하기 전 data
		System.out.println(data);

		bubleSort(data, data.size());
		System.out.println("buble Sort :: " + data);
	}

	private static void bubleSort(ArrayList<Integer> data2, int size) {
		//버블 정렬 코드
		int i , j, tmp = 0;
		
		//전체 데이터를 순차적으로 접근
		// i는 내가 반복문을 돌릴 횟수를 순차적으로 접근
		// 반복문을 돌릴 횟수 -> (size-1) ex. 데이터가 8개면 최대 7번 비교.
		for (i = 0; i < (size - 1); i++)
		{
			//i개의 데이터를 제외하고 처음부터 끝까지 비교 -> 자리바꿈 : 최대값이 마지막 자리에 놓임.
			//(size-1)에 -i를 하는 이유 -> i개 만큼 비교가 완료된 값이 맨 뒤에 정렬되어 있기 때문에 그 부분은 비교할 필요X
			for (j = 0; j < (size - 1) - i; j++)
			{
				//
				if (data2.get(j) > data2.get(j+1))
				{
					// 인덱스 j와 j+1의 값의 위치를 바꿈.
					tmp = data2.get(j);
					data2.set(j, data2.get(j+1));
					data2.set(j+1, tmp);
				}
			}
		}
		
	}

-각 라운드를 진행할 때 마다 뒤에 데이터가 완전하게 정렬되기 때문에 비교할 필요가 없어 배열 크기 - 라운드 횟수 만큼 비교하면 됨.

 

 

<병합정렬>

import java.util.ArrayList;

public class TestSort {

	private static ArrayList<Integer> data;

	public static void main(String[] args) {

		data = new ArrayList<Integer>();
		data.add(3);
		data.add(65);
		data.add(68);
		data.add(53);
		data.add(20);
		data.add(8);
		data.add(48);
		data.add(25);
		data.add(86);
		data.add(4);

		// 정렬하기 전 data
		System.out.println(data);
        
       // 병합정렬
		mergeSort(data, data.size());
		System.out.println("merge Sort :: " + data);

	}

	private static ArrayList<Integer> newData;
	private static void mergeSort(ArrayList<Integer> data2, int size) {

		partition(0, size - 1); // 전체 데이터를 2개로 나누고 병합정렬 수행

	}
	
	private static void partition(int left, int right) {
		// 부분 집합 정렬
		if (left < right) {
			int mid = (left + right) / 2; // 전체 데이터를 2개로 나누기 위해 중간 값을 선정
			partition(left, mid); 		 // 앞부분을 다시 2개로 나눔 (재귀호출로 나눌 수 없는 위치까지 나눔.)
			partition(mid + 1, right);  // 뒷부분을 다시 2개로 나눔 (재귀호출로 나눌 수 없는 위치까지 나눔.)
			merge(left, right); 	   // 정렬
		}
		
	}

	private static void merge(int left, int right) {
		// 병합 정렬 코드
		newData = new ArrayList<Integer>(data); //복사의 개념이 아닌 크기를 같게 만들기 위함.
						// newData = 버퍼 데이터 : 일시적으로 그 데이터를 보관

		// 절반짜리 data(원본 데이터)를 newData에 복사한다.
		for (int i = left; i <= right; i++) {
			newData.set(i, data.get(i));
		}

		int mid = (left + right) / 2;

		int tempLeft = left;
		int tempRight = mid + 1;
		int curIndex = left;

		// newData를 순환하여 왼쪽 절반 값과 오른쪽 절반 값 비교해서
		// 더 작은 값을 원래 리스트(data)에 복사
		while (tempLeft <= mid && tempRight <= right) { //-> left와 right를 비교해서 순서를 바꿔주는 작업
			
			if (newData.get(tempLeft) <= newData.get(tempRight)) {
				data.set(curIndex++, newData.get(tempLeft++));
			} else {
				data.set(curIndex++, newData.get(tempRight++));
			}
		}
		// 왼쪽 절반에 남은 요소들을 원래 리스트(data)에 복사
		int remain = mid - tempLeft;
		//newData에 있는 남은 앞자리 값을 원본 데이터 data에 복사해 넣는 작업 수행
		for (int i = 0; i <= remain; i++) {
			data.set(curIndex + i, newData.get(tempLeft + i));
		}

	}

 

<퀵 정렬>

public class TestSort {

	private static ArrayList<Integer> data;
	private static ArrayList<Integer>[] queue = new ArrayList[10];
    
    public static void main(String[] args) {

		data = new ArrayList<Integer>();
		data.add(3);
		data.add(65);
		data.add(68);
		data.add(53);
		data.add(20);
		data.add(8);
		data.add(165);
		data.add(25);
		data.add(125);
		data.add(4);

		// 정렬하기 전 data
		System.out.println(data);
        
        // 퀵정렬
		quickSort(data, data.size());
		System.out.println("quick Sort :: " + data);
        
        	private static void quickSort(ArrayList<Integer> data2, int size) {
		// 퀵 정렬
		quick(0, size-1);
		
	}

	private static void quick(int left, int right) {
		//튜닝 (제거)
		if (left < right){
			int p = partitionQuick(left, right); //피봇 값의 최종위치를 확정시킴.

			quick(left, p - 1); //피봇 기준 왼쪽 다시 정렬
			quick(p + 1, right); //피봇 기준 오른쪽 다시 정렬
		}
		
	}

	private static int partitionQuick(int left, int right) {
		int pivot = data.get(right); //맨 마지막 값을 피봇 선정
		int i = (left - 1); // p+1이 들어올 경우, 0이 아닌 값이 들어올 수 있기 때문

		for (int j = left; j <= right-1; j++){ // right-1은 피벗을 제외한 마지막 값의 위치 
			//배열 순회하며 피봇이랑 같거나 작은 값 탐색
			if (data.get(j) <= pivot) { 
								
				i++;    
				swap(i, j); //i 인덱스 위치와 교체 
			}
		}

		//partition 구분을 종료 후 pivot의 값을 최종 위치 (i+1)의 값과 교체.
		swap(i+1,right);

		return (i + 1); // pivot의 최종 위치 값을 리턴
	}

	private static void swap(int left, int right) { // left, right는 위치 값
		// 값을 교환하는 메서드
		int tmpValue = data.get(left);
		data.set(left, data.get(right));
		data.set(right, tmpValue);
		
	}

 

<기수 정렬>

public class TestSort {

	private static ArrayList<Integer> data;
	private static ArrayList<Integer>[] queue = new ArrayList[10];
	
	//static initializer -> 클래스 초기화 
	static {
		for (int i = 0; i<10; i++) {
			queue[i] = new ArrayList();
		}
	}

	public static void main(String[] args) {

		data = new ArrayList<Integer>();
		data.add(3);
		data.add(65);
		data.add(68);
		data.add(53);
		data.add(20);
		data.add(8);
		data.add(165);
		data.add(25);
		data.add(125);
		data.add(4);

		// 정렬하기 전 data
		System.out.println(data);
        
        		// 기수정렬
		radixSort(data, data.size());
		System.out.println("quick Sort :: " + data);

	}

		//queue : 0 ~ 9, 총 10개(배열)의 queue(ArrayList로 구현)로 구성된 전체 데이터
	private static void radixSort(ArrayList<Integer> data2, int size) {
		// 기수 정렬
		int radix = 1;
		boolean flag = false;
		// 가장 큰 값을 찾아서 자릿수를 구함. (1, 10, 100, 1000, ...)
		while(true) {
			for (int i = 0; i < data2.size(); i++) {
				if(radix < data2.get(i)) {
					flag = true;
					break;
				}else {
					flag = false;
				}
				
			}
			
			//flag가 참이면 자릿 수를 증가 (ex.1의 자리 -> 10의 자리)
			if(flag) {
				radix = radix*10; //처음부터 시작
				
			}else {
				//radix값 확인 코드
				System.out.println("radix2 = " + radix);
				//더 이상 radix보다 큰 값이 없으면 while을 빠져나감.
				break;
			}
		}
		// 가장 작은 자릿수부터 차례대로 정렬(1의자리 한 다음 10의 자리 순..)
		for(int i = 1; i<=radix; i*=10) {
			for(int j=0; j<size; j++) {
				int k;
				if(data2.get(j)<i) 
					k=0;
				else 
					k = (data2.get(j) / i) % 10;
				queue[k].add(data2.get(j));
				
			}
//			//i 값 확인 코드
//			for(ArrayList q : queue) {
//				System.out.println("radix = " + i);
//			}
			int idx = 0;
			for(int j=0; j<10; j++) {
				
				while(!queue[j].isEmpty()) {//튜닝 포인트 : for-each문으로 고쳐보기
					data2.set(idx, queue[j].remove(0));
					idx++;
				}
			}
		}
		
	}