본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘-이론] 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort) 이란? 이미 정렬되어 있는 i개 짜리의 배열에 하나의 원소를 더 더하여 정렬된 i+1 개의 배열을 만드는 과정을 A[n] 까지 반복하는 알고리즘 이다. 차이점이 있다면 지금까지 했던 선택 정렬 이나 버블 정렬은 n 개의 배열에서 시작하여 하나씩 원소를 줄이는데 반하여 삽입 정렬은 그 크기를 하나씩 늘리는 정렬이다. 하지만 선택 정렬이나 버블 정렬에 비하여 구현하기 조금 까다롭다는 점이 있다. 백문이 불여일타 라고 pseudo 코드를 한 번 가볍게 보고 직접 생각해보자. insertionSort(A[], n){ .... 1 for i A[i-1] 이면 A[i]는 A[1..i-1] 의 모든 원소보다 크므로 그냥 제자리에 두고 그렇지 않을 경우 왼쪽부터 차례대로 A[i].. 2019. 11. 23.

[알고리즘-이론] 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort)이란? 버블 정렬은 인접한 두 원소를 비교하여 큰/작은 수를 기준으로 자리를 교환하는 방식으로 정렬하는 알고리즘을 뜻한다. 선택정렬과 같이 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는데 제일 큰 원소를 옮기는 방법의 차이가 있다. 버블정렬을 간단하게 설명하자면. 라운드의 순서별로 임의의 포인터를 만들어 뒷 값과 비교를 하는 과정을 반복한다. 만약 뒷 값보다 크게되면 자리를 옮겨 그 다음 값과 비교하고 크지 않다면 포인터를 뒤로 넘겨 포인터가 정렬되지 않은 배열의 끝까지 도달했을 때 한 라운드가 종료된다. pseudo 코드를 먼저 보자면 bubbleSort(A[], n){ .... 1 for last 7과 22중 22가 더 크므로 포인터를 22로 옮긴다. 결과: {7,.. 2019. 11. 23.

[알고리즘-이론] 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 이란? 선택정렬은 가장 원리가 간단하면서 알고리즘의 효율로 봤을때 결코 좋은 알고리즘이로 볼 수 없다.(시간 복잡도로 본다면) 원리는 배열 원소에가 가장 큰/작은 수를 배열의 끝으로 보내는 작업을 계속 반복하는 것이다. 선택정렬에는 크게 2가지가 존재하고 정렬 목적에 따라 또 2가지로 나뉘게 된다. 최대 선택 정렬(오름차순) : 큰 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법 최대 선택 정렬(내림차순) : 작은 수를 가장 오른쪽에 위치시키고 배열의 인덱스를 1씩 줄이는 방법 최소 선택 정렬(오름차순) : 작은 수를 가장 왼쪽에 위치시키고 배열의 인덱스를 1씩 늘리는 방법 최소 선택 정렬(내림차순) : 큰 수를 가장 왼쪽에 위치시키고 배열의 인덱스.. 2019. 11. 23.

이전 1 ··· 22 23 24 25 다음

티스토리툴바