정렬 알고리즘

- 버블정렬

인접한 요소들끼리 비교 , 교환 과정의 반복 시간 복잡도 O(n^2)

		for(int k=0;k<arr.length;k++) {
			for(int j=0;j<arr.length-1;j++) {
				int temp =0;
				if(arr[j]>arr[j+1]) {
					temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
					System.out.print(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]+" "+arr[4]);
				}
		}System.out.println(" ");

 

- 선택정렬 : 배열요소에서 최솟값을 찾아 제일 앞에 가져다 놓고 이미 정렬된 값을 제외한 요소들에서 최솟값을 찾아 그 다음 앞에 가져다놓는 작업 반복 시간 복잡도 O(n^2)

배열의 제일 왼쪽부터 작은 값이 정렬됨.

		for(int i=0;i<arr.length;i++) {
			int temp = 0;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[i] > arr[j]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
				System.out.print(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]+" "+arr[4]+" ");

			}
			System.out.println(" "+ count);

 

- 삽입정렬 : 인덱스 1부터 시작해서 기준이 되는 좌측의 요소들과 비교해서 swap해나감. 시간복잡도 O(n^2)

N사이클 수행 후 N+1개의 데이터가 정렬됨.

	for(int j=1;j<arr.length;j++) {
			int temp =0;
		for(int i=0;i<j;i++) {
			if(arr[i] > arr[j]) {
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
				System.out.print(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]+" "+arr[4]+" ");

			}

-퀵 정렬 : pivot값을 기준으로 좌측에는 작은 값, 우측에는 큰 값을 계속해서 넣어가는 방식
n만큼 partition을 나누는데 나눌 때마다 데이터가 절반씩 줄어드니까 O(nlogn)의 평균 시간복잡도를 가짐. 최악은 O(n^2).

(한 번 돌 때마다 검색할 데이터가 절반씩 떨어지면 log n)

import java.io.BufferedReader;
import java.io.InputStreamReader;


class Solution{ //퀵 정렬 구현하기 ~~~
	public static void quicksort(int []arr) {
		quicksort(arr,0,arr.length-1);
	}
	public static void quicksort(int []arr,int start,int end) {
		int part2 = partition(arr,start,end);
		
		if(start < part2 -1) {
			quicksort(arr,start,part2-1);
		}
		if(part2 < end) {
			quicksort(arr,part2,end);
		}
	}
	public static int partition(int []arr, int start, int end) {
		int pivot = arr[(start+end)/2];
		while(start <=end) {
			while(arr[start] < pivot) start++;
			while(arr[end] > pivot) end --;
			
			if(start <= end) {
				swap(arr,start,end);
				start++;
				end--;
			}
		}
		return start; //새로 나눌 오른 쪽 파티션의 첫번째 인덱스가 들어감
	}
	public static void swap(int []arr,int start,int end) {
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;
	}
	public static void printArray(int []arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
	}
	public static void main(String args[]) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int arr[] = new int[T];
		for(int i=0;i<T;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		quicksort(arr);
		printArray(arr);
	}
}