본문 바로가기

[정렬] 삽입정렬 (Insertion Sort) * 삽입정렬 (Insertion Sort) - 정렬 대상을 두 부분으로 나누어 정렬되지 않은 부분에 있는 데이터를 정렬된 부분의 특정 부분에 삽입해 가면서 정렬을 진행(key 값 을 선택하여 이미 정렬된 숫자 사이에 삽입) [시간복잡도]- 최선의 경우 O(n) [1, 2, 3, 4] 5, 6, 7, 8정렬된 요소들과 정렬되지 않은 요소가 전체적으로 오름차순 정렬을 이루고 있는 경우- 최악의 경우 O(n^2) [5, 6, 7, 8] 4, 3, 2, 1 정렬된 요소의 맨 앞에 있는 값이 정렬되지 않은 요소들의 값보다 항상 크고,정렬되지 않은 요소들의 값이 내림차순인 경우 ※ 오름차순 정렬에 대한 설명.input = [47, 15, 36, 26, 27, 2] 자~ 이제 정렬을 시작합니다!전체 요소들 중 제일 .. 더보기
[정렬] 선택정렬 (Selection Sort) * 선택정렬 (Selection Sort) - 선택을 해서 정렬하는 알고리즘 - 최소선택정렬 : 가장 작은 숫자를 선택(오름차순) - 최대선택정렬 : 가장 큰 숫자를 선택(내림차순) - 개선된 선택 정렬(기존의 선택정렬은 정렬하기 위한 배열이 하나 더 필요함) - 최선, 최악의 경우가 따로 존재하지 않음 - 시간복잡도 O(n^2) ※ 오름차순 정렬에 대한 설명. input = [15, 36, 26, 27, 2, 46] - 정렬되지 않은 요소들의 맨 앞에 있는 요소를 minimum으로 설정한다. - 전체 요소들을 검사하면서 minimum(=15) 보다 작은지 비교한다. - minimum(=15) 보다 작은 숫자 2를 발견하게 되면 'minimum = 2' 로 만들어준다. - 나머지 요소들을 계속 검사하면서.. 더보기
[정렬] 버블정렬 (Bubble Sort) * 버블정렬 (Bubble Sort) - 인접한 두개의 데이터를 비교하면서 정렬- 최선, 최악의 경우가 따로 존재하지 않음- 시간복잡도 O(n^2) ※ 오름차순 정렬에 대한 설명.input = [3, 44, 38, 5, 47, 15] - 다음과 같이 맨 처음의 숫자와 그다음의 숫자를 비교해 둘 중 더 큰 숫자를 오른쪽으로 이동한다.- '3'과 '44' 중 44가 더 크므로 자리이동이 발생하지 않는다. - 다음으로 두번째 숫자인 '44'와 '38'을 비교한 경우 '44'가 더 크므로 오른쪽으로 자리이동이 발생한다. ...- 위처럼 계속해서 좌, 우 숫자를 계속해서 비교하면서 숫자를 정렬시켜 나간다.- 이렇게 한번 모든 모든 숫자를 비교하게 되면 아래 그림처럼 제일 큰 숫자가 맨 뒤에 위치하게 된다. - 이.. 더보기
알고리즘 시작 * 알고리즘 이란?문제를 해결하는 절차적인 방법 * 정렬문제N개의 숫자가 입력으로 주어졌을 때, n 개의 숫자들의 크기대로 출력을 내보내는 것 * 시간 복잡도[빅오 표기법 - Big O]- 점근적 상한선, 보편적인 표기법- 최악의 상황을 표현 (아무리 나빠도 이것보다 나쁠 수 없다!)-> 아래로 갈수록 느리고 효율이 떨어진다. [빅오메가 표기법 - Big Omega]- 점근적 하한선- 최선의 상황을 표현 (아무리 좋아도 이것보다 좋을 수 없다!) [빅세타 표기법 - Big Theta]- 점근적 하한선 ∧ 점근적 하한선- 평균적 상황을 표현 (아무리 좋거나 나빠도 비교하는 함수의 범위안에 있다.) 더보기