tec / alogrithm
2분 읽기 (나에 대하여 331 단어)

[알고리즘] 5. 고급 정렬(합병정렬, 퀵정렬)

1. 로그 개념과 효율성

log2 16=4;
logx y = N;
x^n=y;
nlog n <- n이커질수록 o(n)과 속도 차이가 크다

2. 고급정렬 종류

2.1 합병정렬

정렬할 값을 반으로 나눠 각각 정렬 후 두 정렬을 크기순으로 합침

2.1.1 고급정렬 예제

1) 아래 배열 정렬

4 14 8 23 11

2) 반으로 나누기->각 값이 하나씩 있을때까지

4 14 8 3 23 11
4 14 8 3 23 11
4 14 8 3 23 11

3) 각각 크기순으로 배열 합치기

4 14 8 3 23 11
4 8 14 3 11 23
3 4 8 11 14 23

2.1.2 합병정렬 시간복잡도

1) 왼쪽 /오른쪽 합병정렬 T(n/2) +T(n/2) => n
2) 두 배열 합치기 o(n)
3) T(n)=2*T(n/2)+O(n)
이걸 풀면…
T(n)=O(nlogn)

2.1.3 합병정렬 재귀함수 디자인

1) 함수 정의
2) 기저조건 s>=e이면 retrun
3) mearge(arr, s, e)
mearge(arr, s, mid)
mearge(arr, mid+1, e)

2.1.4 합병정렬 구현

1
2


2.2 퀵정렬

임의의 값 하나를 기준으로 기준값보다 큰건 오른쪽 작은건 왼쪽으로 보내기

2.2.1 예시

1) 아래 배열 퀵정렬

3 1 5 4 2

2) 배열 제일 앞숫자3 기준 정렬

1 2 3 5 4

3-1) 3기준 앞 배열 제일 앞 숫자1로 정렬

1 2 3 5 4

3-2) 3기준 뒤 배열 중 가장 앞 숫자 5기준으로 정렬

1 2 3 5 4

2.2.2 퀵정렬 시간복잡도

평균적으로는 O(nlogn) 가장 오래 걸리면 O(n^2)

2.2.3 퀵정렬 구현

1
2


2.3 힙정렬

트리구조를 이용한 정렬 나중에 나옴!

tec / alogrithm
3분 읽기 (나에 대하여 433 단어)

[알고리즘] 1. 정렬 기초(선택정렬, 삽입정렬, 버블정렬)

1.정렬

오름차순, 내림차순

1.1 정렬의 종류

  1. 선택정렬
  2. 삽입정렬
  3. 버블정렬

1.1.1 선택정렬 예시

배열을 순서대로 탐색하면서 최소값을 앞으로 이동시킴

0) 주어진 배열
2 5 6 7 1 3
1) 첫번째 정렬(1과 2 자리변경)
1 5 6 7 2 3
2) 두번째 정렬(배열2부터 최소값찾기/2와 5자리 변경)
1 2 6 7 5 3
3) 세번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)
1 2 3 7 5 6
4) 네번째 정렬(배열4부터 최소값찾기/5와 7자리 변경)
1 2 3 5 7 6
5) 다섯번째 정렬(배열5부터 최소값찾기/6와 7자리 변경)
1 2 3 5 6 7
6) 선택정렬끝!!

1.2.1 삽입정렬

기준 배열과 나머지 배열 비교하여 작은것 것을 앞으로 바꿈

ex)

0) 주어진 배열
2 5 9 1 6
1) 첫번째 정렬

(2와 5비교 유지)

2 5 9 1 6

(2와 9비교 유지)

2 5 9 1 6

(2와 1비교 1과 2위치 변경)

1 5 9 2 6

(1과 6비교 유지)

1 5 9 2 6
2) 두번째 정렬(배열2부터 최소값찾기/2와 5자리 변경)

(5와 9비교 유지)

1 5 9 2 6

(5와 2비교 자리변경)

1 2 9 5 6

(2와 6비교 유지)

1 2 9 5 6
3) 세번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)

(5와9비교 유지)

1 2 5 9 6

(5와 6비교 유지)

1 2 5 9 6
4) 네번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)

(9와9비교 변경)

1 2 5 6 9
5) 삽입정렬끝!!

1.3.1 버블정렬

인접한 두 원소 비교 해서 큰 수를 뒤로 보냄

ex)

0) 주어진 배열
3 2 5 1 4
1) 첫번째 정렬

(3과 2비교 자리 바꿈)

2 3 5 1 4

(3과 5비교 유지)

2 3 5 1 4

(5와 1비교 자리 변경)

2 3 1 5 4

(5와 4비교 변경 > 5자리 확정)

2 3 1 4 5
2) 두번째 정렬

(2와 3비교 유지)

2 3 1 4 5

(3와 1비교 자리변경)

2 1 3 4 5

(3와 4비교 유지 > 4자리 확정)

2 1 3 4 5
3) 세번째 정렬

(2와1비교 변경)

1 2 3 4 5

(2와 3비교 유지 > 3자리 확정)

1 2 3 4 5
4) 네번째 정렬

(1와2비교 유지 > 2자리 확정)

1 2 3 4 5
5) 버블정렬끝!!
tec / alogrithm
2분 읽기 (나에 대하여 240 단어)

[자료구조] QuickSort(퀵정렬) - Java

1. QuickSort(퀵정렬)

1.1 퀵정렬 이란?

  1. 배열중에 임의의 한 값을 선택해 그 기준값을 기준으로 작은건 왼쪽, 큰건 오른쪽에 정렬.

문제.2751 [백준] 수 정렬하기 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		quickSort(arr);
		for (int i : arr) {
			System.out.println(i);
		}
	}

	public static void quickSort(int[] arr) {
		sort(arr, 0, arr.length - 1);
	}

	private static void sort(int[] arr, int start, int end) {
		if (start >= end)
			return;

		int mid = partition(arr, start, end);
		sort(arr, start, mid - 1);
		sort(arr, mid, end);
	}

	private 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;
	}

	private static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
  • 4,3,2,1,0 배열을 정렬할때 아래 순으로 졍렬된다.
4 3 2 1 0
0 3 2 1 4
0 1 2 3 4
tec / alogrithm
2분 읽기 (나에 대하여 264 단어)

[자료구조] MeargeSort(병합 정렬) - Java

1. 병합정렬(MeargeSort)

1.1 병합 정렬이란?

  1. 정렬할때 가장 작은 단위로 나눠서 정렬후(sort) 병합(mearge)하는 것을 말한다.

문제.2751 [백준] 수 정렬하기 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


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

public class Main {

	public static void mergeSort(int[] arr) {
		mergeSort(arr,  0, arr.length - 1);
	}

	public static void mergeSort(int[] arr, int start, int end) {

		int[] tmp = new int[arr.length];
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(arr, start, mid);
			mergeSort(arr,  mid + 1, end);
			mearge(arr, start, mid, end);
		}

	}

	private static void mearge(int[] arr, int start, int mid, int end) {
		int[] tmp = new int[arr.length];
		for (int i = start; i <= end; i++) {
			tmp[i] = arr[i];
		}
		int part1 = start;
		int part2 = mid + 1;
		int index = start;
		while (part1 <= mid && part2 <= end) {
			if (tmp[part1] <= tmp[part2]) {
				arr[index] = tmp[part1];
				part1++;
			} else {
				arr[index] = tmp[part2];
				part2++;
			}
			index++;
		}

		for (int i = 0; i <= mid - part1; i++) {
			arr[index + i] = tmp[part1 + i];
		}

	}

	private static void printArray(int[] arr) {
		for (int i : arr) {
			System.out.println(i);
		}
	
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		mergeSort(arr);
		printArray(arr);
	}
}
  • 4,3,2,1 배열을 정렬할때 아래 순으로 졍렬된다.
4 3 2 1
3 4 2 1
3 4 1 2
1 2 3 4
팔로우

카테고리

아카이브

태그 클라우드

Markdown alogrithm blog disque framework github google-analytics hexo java java의 정석 jekyll network noip react spirng boot spring sql tec websocket 골든서클 공유기 눈 도메인 리엑트 마크다운 무지개 미국 빙하 소켓통신 숙소 시간복잡도 아이슬란드 알고리즘 여행 옐로우스톤 오로라 유럽 자료구조 재귀함수 정렬 폭포 프레임워크 해변

카테고리

아카이브

태그 클라우드

Markdown alogrithm blog disque framework github google-analytics hexo java java의 정석 jekyll network noip react spirng boot spring sql tec websocket 골든서클 공유기 눈 도메인 리엑트 마크다운 무지개 미국 빙하 소켓통신 숙소 시간복잡도 아이슬란드 알고리즘 여행 옐로우스톤 오로라 유럽 자료구조 재귀함수 정렬 폭포 프레임워크 해변
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×