정렬 알고리즘

📔버블정렬
시간복잡도:n(n-1)/2 -> O(n^)

1. 이웃한 요소와 비교하고 교환
   https://www.jungol.co.kr/problem/1157

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

	int[] x = new int[N];	
	StringTokenizer st = new StringTokenizer(br.readLine());
	int t=0;
	
	
	
	for (int i = 0; i < N; i++) {
		x[i] = Integer.parseInt(st.nextToken());
		
	}
	
	for (int i = 0; i < N-1; i++) {
		for (int j = 0; j<N-1 ; j++) {
			if(x[j] > x[j+1]) 	{
				t= x[j+1];
				x[j+1] =x[j];
				x[j] = t;
			}

			
		}
		for (int j = 0; j < N; j++) {
			System.out.print(x[j]+" ");
			
			
		}
		System.out.println();
	}
	
	
		
	}



	
}
```

📔선택정렬

시간복잡도 O(n^)
1. 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 저장
2. 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환

![](https://velog.velcdn.com/images/cjy205/post/13ab4d89-2112-4043-8a82-571b006bdd53/image.png)


https://www.jungol.co.kr/problem/1146

```java
import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class J1146 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] x = new int[n];

	StringTokenizer st = new StringTokenizer(br.readLine());

	for (int i = 0; i < n; i++) {
		x[i] = Integer.parseInt(st.nextToken());
	}
	
	
	int min= 0;
	int minvalue=0;
	
	for (int i = 0; i < n-1; i++) {
		min =i;
		minvalue = x[min];
		
		for (int j = i+1; j < n; j++) {
			if(x[j] < minvalue)
				min =j;
				minvalue=x[min];
			
		}
		int temp=x[i];
		x[i]=minvalue;
		x[min]=temp;
		
		
		for (int j = 0; j < n; j++) {
			System.out.print(x[j]+" ");
			
		}
		System.out.println();
	}
	
	
}

} ```

📔삽입 정렬

시간복잡도 :O(n^)
1. 삽입정렬은 두 번째 요소부터 선택하여 진행
2. 예를들어 배열이 4 6 1 7 3 9 8 이면 ,이때 4는 6보다 앞쪽에 위치해야 하므로 앞쪽에 삽입

주의 : 자바는 배열이 연속적으로 할당되어있어서 중간에 값 삽입이 불가
해결 : 뒷쪽에 있는 데이터를 tmp 변수에 저장한 후 x[j]=x[j-1]과 같이 앞쪽에 있는 데이터를 뒤에 복사해서 값을 집어 넣음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());	
		int[] x = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		for (int i = 0; i < n; i++) {
			x[i] = Integer.parseInt(st.nextToken());
		}
		
		
		for (int i = 1; i < n; i++) {
			int j;
			int tmp =x[i];
			for (j = i; j >0 && x[j-1] >tmp; j--) {
				x[j] = x[j-1];
			}
			
			x[j]=tmp;
			
			for (int k = 0; k < n; k++) {
				System.out.print(x[k]+" ");			
				
			}
			System.out.println();
		}
	}

}

📔퀵 정렬