자바 Sort 구현하기

깃허브 주소

1. Selection Sort

	public int[] sort_my(int[] sample, int digit) {

		System.out.println(count_my + " : " + Arrays.toString(sample));
		count_my++;

		if(digit == 1) {
			return sample;
		} else {

			int max = 0;

			for(int i = 0; i < digit; i++) {
				if(sample[max] < sample[i]) { max = i; }
			}

			int temp = sample[max];
			sample[max] = sample[digit-1];
			sample[digit-1] = temp;

			this.sort_my(sample, digit-1);

		}



		return sample;
	}

2. Merge Sort

	public int[] temp;
	public int[] sort_my(int[] sample, int left, int right) {


		if((right-left) == 1) {
			merge(sample, left, right, right);
		} else if(right == left) {
			return sample;
		} else {
			this.sort_my(sample, left, (right-left)/2+left);
			this.sort_my(sample, (right-left)/2+left+1, right);
			this.merge(sample, left, (right-left)/2+left+1, right);
		}

		return temp;
	}



	public int[] merge(int[] sample, int left, int digit, int right) {

		this.temp = new int[sample.length];

		int left_standard = left;
		int digit_standard = digit;

		for(int i = left_standard; i <= right; i++) {
			if(left < digit_standard && digit <= right) {
				if(sample[left] > sample[digit]) {
					temp[i] = sample[digit];
					digit++;
				} else {
					temp[i] = sample[left];
					left++;
				}
			} else if(left < digit_standard) {
				temp[i] = sample[left];
				left++;
			} else if(digit <= right) {
				temp[i] = sample[digit];
				digit++;
			}
		}

		for(int i = left_standard; i <= right; i++) {
			sample[i] = temp[i];
		}

		System.out.println(count_my + " : " + Arrays.toString(sample));
		count_my++;

		return sample;
	}

3. Quick Sort

	public int[] sort_my(int[] sample, int left, int right) {


		if(right > left) {
			int pivot = quick(sample, left, right);
			sort_my(sample, left, pivot-1);
			sort_my(sample, pivot+1, right);
		}

		return sample;
	}


	private int quick(int[] sample, int left, int right) {
		// 가장 왼쪽, 가장 오른쪽, 피봇 3가지 필요
		// 피봇은 가장 오른쪽으로 설정

		int pivot = right;
		int left_standard = left;
		int right_standard = right;
		int[] temp = new int[sample.length];

		for(int i = left_standard; i < right_standard; i++) {
			if(sample[pivot] >= sample[i]) {
				temp[left] = sample[i];
				left++;
			} else {
				temp[right] = sample[i];
				right--;
			}
		}

		pivot = left;
		temp[pivot] = sample[right_standard];
		for(int i = left_standard; i <= right_standard; i++) {
			sample[i] = temp[i];
		}

		System.out.println(count_my + " : " + Arrays.toString(sample));
		count_my++;


		return pivot;

	}