뭘 배웠지?

선택 알고리즘 n개의 원소가 불규칙하게 저장된 배열에서 i번재 큰(or 작은)원소를 찾는 알고리즘 정렬과 비슷하다 두 가지 알고리즘 평균적으로 선형시간이 소용되는 알고리즘 최악의 경우에 선형시간이 소요되는 알고리즘 평균적으로 선형시간이 소용되는 알고리즘 배열 A에서 i 번째 원소 찾기 원소가 하나뿐인 경우, 하나 리턴 원소가 다수의 경우, 파티션(퀵 정렬)을 통해 중간값이 몇 번째인지 확인 중간값이 i와 같을 경우, A[파티션 통해 얻은 중간]값 리턴 중간값이 i보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀 중간값이 i작을 경우, 왼쪽 그룹으로 범위를 좁혀 재귀 예시 1 2번째 작은 원소 찾기 [31] [8] [48] [73] [11] [3] [20] [29] [65] [15] 마지막수 15를 기준으..

기수정렬(Radix Sort) k이하의 자릿수를 가진 자연수인 경우 각 자릿수별로 정렬 숫자를 부분적으로 비교 기수의 기란? 기수에서 기는 기(Radix), 특정 진수를 나타낸다 10진수의 기: 0 ~ 9 2진수의 기: 0, 1 예시 가장 낮은 자릿수(1의 자리)를 비교 그 다음 낮은 수(10의 자리) 비교 그 다은 자릿수(100의 자리) 비교 하면서 작은수부터 적어주면 된다. 어디서 쓰면 좋을까? 많은 숫자로 되어있는 상용 데이터 베이스에서 유용 주민등록번호, 계좌번호, 전화번호, 인터넷 주소 등 파이썬으로 구현하면 이렇다(그저 따라해서 이해 못했지만) def radix_sort(A): RADIX = 10 maxLengh = False tmp, placement = -1, 1 while not maxL..

계수정렬(Counting Sort) 각 항목이 몇개씩 있는지 세는 작업을 하면서 선형시간에 정렬 한계 정수나 정수로 표현할 수 있는것만 정렬가능 방법 최대값까지 배열 생성 입력원소의 발생 횟수를 세어 저장 예시 입력 배열: [0] [5] [4] [4] [1] [3] [2] [5] [1] [4] [6] 입력 원소의 최대값까지 카운트(Count) 배열 생성 위의 예에서는 0~6까지 정수, 7개를 가진 카운트 배열이 생성된다. 1. 카운트 배열 7개 각 원소의 발생 횟수를 세어 저장 0 원소의 개수 한번, 1이 두번, 2가 한번 등 6까지 그럼 카운트 배열은 이렇다 [1] [2] [1] [1] [3] [2] [1] 2. 카운트 배열의 값을 누적하여 저장 다시 카운트 배열의 값을 누적해서 만들어준다 [1] [2..

트리 정렬(Tree Sort) 이진탐색트리를 이용해 정렬한다 이진트리? 트리의 모든 노드의 차수가 2이하 탐색 요건 모든 노드의 키는 서로 다른 유일한 키 왼쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 작다 오른쪽 서브트리에 있는 노드들의 키는 루트 노드의 키보다 크다 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색트리

힙 정렬(Heap Sort) 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면서 항상 루트 노드의 원소를 삭제하며 반환 힙(Heap) 이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기위해, 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조 힙 종류 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

퀵 정렬 기준 값을 중심으로 왼쪽과 오른쪽 부분집합으로 정렬 기준 값을 피봇(Pivot)이라고 함 첫번째 가운데 혹은 마지막에 위치한 원소 선택 분할 기준값(피봇) 중심으로 2개의 부분집합으로 분할 정복 기준값 기준 작은 원소 왼쪽, 큰 원소 오른쪽으로 부분집합의 크기가 1일 될때까지 반복 규칙 Left는 피봇보다 작으면 통과, 크면 정지 Right는 피봇보다 크면 통과, 작으면 정지 예시 첫 번째 원소 52를 피봇이라고 하자 52(피봇), 33, 87, 47, 99, 4, 65, 26, 77 33을 Left로 표시, 77은 Right로 표시 52와 33(Left) 비교해보니 33이 작다 그러니 Left를 87로 52와 77(Right) 비교해보니 77이 크다 그러니 Right을 26으로 이동 현재 상황..

셸 정렬 주어진 자료에 매개 변수 h 길이를 갖는 부분집합으로 나누고, 삽입정렬 수행 매개변수 h값을 줄이며 반복, 매개 변수 h 값이 1이 되면 정렬 완성 부분집합 만드는 방법 부분집합 기준 간격을 h에 저장 한단계씩 h 값을 감소시키고 셸 정렬 호줄 h1가 1이 될 때까지 반복 예시 44, 88, 62, 38, 19, 49, 27, 73가 있다 매개변수를 원소 개수의 반으로 하는 경우 전체 원소 8개니까 매개 변수 h는 4 시작! 4간격씩 떨어져 있는 녀석들을 모아서 부분집합을 만든다 그 말은 44에서 오른쪽으로 4번 떨어진 19를 하나의 부분집합, 88에서 4번 떨어진 49를 부분집합으로 ... 나머지도 똑같이 부분집합 만들때 중요한 포인트 부분집합 할 때 삽입 정렬을 한다 이렇게 만들어진다 19,..

병합정렬 여러개의 정렬된 자료를 병합해서 하나로 만든다 부분집합으로 분할하고, 각 부분집합에서 정렬을 완료하고 정렬된 부분집합을 결합 2-way 병합: 2개의 정렬된 자료를 1개로 병합 n-way 병합: n개의 정렬된 자료를 1개로 병합 2-way만 한번 알아보자 같은 크기의 부분집합 2개로 분할 부분집한 원소들 정렬 1개로 병합 예시 분할 단계 44, 88, 62, 38, 19, 49, 27, 73이 있다 이렇게 4개씩 2개로 나눠보자 44, 88, 62, 38 그리고 19, 49, 27, 73 왼쪽의 44, 88, 62, 38을 또 나눠보자 44, 88 그리고 62, 38 오른쪽 19, 49, 27, 73도 나눠보자 19, 49 그리고 27, 73 이제 각자 1개씩 나눈다 44 / 88 / 62 / ..

삽입 정렬 정렬이 필요한 요소를 뽑아서 적당한 곳에 삽입 두 부분으로 나눈다, 정렬된 집합과 정렬되지 않은 집합으로 가정 부분집합 S: 정렬된 원소 부분집합 U: 정렬안된 원소 U의 원소를 하나씩 꺼내서 S의 마지막 원소부터 비교해서 위치를 찾아 삽입 S는 하나씩 늘어나고, U는 하나씩 줄어든다 예시 S(정렬된 자료)= {44} U(정렬안된 녀석들) = {88, 62, 38, 19, 49} 먼저 U의 88을 S의 44와 비교후 88이 크니까 44뒤에 삽입 그럼 이렇게 된다 S = {44, 88} U = {62, 38, 19, 49} 그다음 62를 88과 비교한다, 62가 작으니 다음으로 다음 44와 비교한다, 62가 크니 44뒤에 집어넣는다 S = {44, 62, 88} U = {38, 19, 49} 이..

버블 정렬 집합 내의 이웃 요소끼리 교환하는 정렬 1. 44 88 62 38 19 49로 시작! 44 88 비교 88이 커서 교환 x 88 62 비교 88이 커서 88을 뒤로 44 62 88 38 19 49로 다시 시작 88 38 비교 88이 커서 38 뒤로 이렇게 쭉 비교 44 62 38 19 49 88이 되면 88은 정렬 완료 2. 44 62 38 19 49 만 다시 시작 끝날때 까지 비교 레코드가 많이 불려진다. 별로 좋지 않아 보이네