Joon's Blog Joon's Blog

알고리즘 병합정렬(Merge sort) 간단 요약 가정) Array[8]= { 20, 18, 50, 40, 9, 19, 5, 25 } 을 오름차순으로 정렬한다. 1. 배열을 반으로 분할 2. 반으로 나누어진 배열들을 다시 반으로 분할한다. 3. 각각의 배열의 인덱스가 하나만 남을 때까지 분할 4. 하나씩 남은 배열들을 빈배열에 오름차순으로 합친다. -> 병합정렬은 이해하기 까다로울수 있다. 복잡하지만 이렇게 하는 이유는 시간복잡도를 줄이기 위해서 이다. 예를 들어 n*n 의 시간복잡도를 갖고 있다고 하자 10개 의 배열을 정렬하는데 걸리는 시간은 100 이된다. 하지만 반으로 쪼개서 5개씩 정렬후 합치는 작업을 한다면 25 + 25 = 50 이라는 시간이 걸린다. 이런 부분에서 분할정복이 강함을 알 수 ..

알고리즘 버블정렬(Bubble sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 특징) 선택정렬은 앞에서 부터 작은수를 정렬시키지만 버블정렬은 뒤에서 부터 큰수를 정렬시킨다. 1. 첫번째 데이터 15와 두번째 데이터 11을 비교한다. 2. 15가 더 크기 때문에 서로 자리를 바꿔준다. 3. 다시 한칸 앞으로 이동해서 두번째 15 와 1을 비교한다. (2번에서 15가 두번째 데이터로 이동한상태) 4. 이번에도 15가 더 크기 때문에 서로 자리를 바꾼다. (현재 상태 { 11, 1, 15, 3, 8 } ) 5. 1회차가 끝나면 { 11, 1, 3, 8, 15 } 형태가 되고 최대값이 마지막 배열에 위치한다. 6. n 번 반복 상세 설명 가정) Arr..

알고리즘 선택정렬(Selection sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 1. 0번 부터 4번 데이터 중 최솟값을 찾아 0번 데이터와 스왑한다. 2. 1번 부터 4번 데이터 중 최솟값을 1번 데이터와 스왑한다. 3. n번 반복 상세 설명 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 가장 먼저 전체 인덱스 중 최솟값을 찾는다. 최솟값 1을 첫번째 인덱스와 스왑한다. 그 다음 두번째에서 네번째 데이터 중 최솟값을 찾는다. 최솟값 3을 두번째 데이터 와 스왑한다. 여기까지 하면 두번째 데이터 까지 오름차순 정렬이 완성된다. 이렇게 n번 반복하면 오름차순 정렬이 완성된다 시간복잡도 코드 123456..

알고리즘 삽입정렬(insertion sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 1. Array[1] 을 key 로 지정한다. 2. Array[0] 가 key보다 크면 오른쪽 쉬프트 , key보다 작으면 Array[0] 앞에 key를 삽입. 3. key의 인덱스를 하나씩 증가시키며 반복. 상세 설명 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 가장 먼저 두번째 데이터를 key 로 지정한다. 그리고 가장 인접한 데이터 부터 비교하여 이전 데이터가 key 값 보다 큰경우 오른쪽으로 이동 key 값 보다 작은 경우 이전 데이터 앞에 key 삽입 첫번째 데이터가 key 값보다 크기 때문에 첫번째 데이터를 ..