CS/DataStructure11 [자료구조] 버블정렬 with JAVA [자료구조] 버블정렬 with JAVA 1. 버블정렬이란? - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식 - 첫 번째 원소부터 마지막 원소까지 반복하면 가장 큰 원소가 마지막 자리에 온다. [예시] 1) 인접한 두 원소를 비교하여 자리를 교환하는 작업을 한다. 이 작업이 완료되면 가장 큰 수가 맨 마지막에 들어온다. 2) 맨 마지막을 제외하고 첫 번째 칸부터 다시 비교를 시작한다. 이렇게 되면 뒤에서 두 번째 칸에 두 번째로 큰 수가 들어온다. 3) 위와 같은 형태로 진행하면 n-i 칸에 i번째로 큰 수가 온다. 4) .... 5) 정렬 완료! - 코드를 확인하자! 2. 버블정렬의 시간복잡도 - i번째 원소는 n-i번 비교하게 되므로 비교 횟수는 아래와 같다. - 시간복잡도는 O(n^2) 이다.. 2018. 4. 11. [자료구조] 선택정렬 with JAVA [자료구조] 선택정렬 with JAVA 선택정렬 - 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다. [예시] 1) 기준 위치 첫 번째 - 전체 원소 중 가장 작은 원소를 찾아 선택한 후 첫 번째 원소와 자리를 교환한다. 2) 기준 위치 두 번째 - 정렬된 첫 번째를 제외한 나머지 원소 중 가장 작은 원소 선택한 후 두 번째 원소와 자리 교환한다. 3) 기준 위치 세 번째 - 정렬된 1, 2번째를 제외한 나머지 원소 중 가장 작은 원소를 선택한 후 세 번째 원소와 자리를 교환한다. ... - 코드를 보면 더욱 쉽게 이해된다! - 시간 복잡도 [예시]를 참고하여 과정을 들여다보면 규칙을 하나 찾을 수 있다. i단계에서는 i번째 기준으로 n-i개 원소를 비교하게 된다. 즉, 전체 비교횟수.. 2018. 4. 11. [자료구조] 정렬과 선택정렬 [자료구조] 정렬과 선택정렬 정렬의 개념 - 순서 없이 배열되어 있는 자료들을 오름차순(작은 것부터 큰 것)이나 내림차순(큰 것부터 작은 것)으로 재배열 하는 것 - key : 기준이 되는 특정 값 [Ex] 학생의 성적 나열에서 키는 '총점' 정렬방법의 분류 - 정렬 방법은 실행 방법, 수행 장소에 따라 분류할 수 있다. [실행 방법에 따른 분류] * 비교식 정렬(Comparative Sort) : 한 번에 2개씩 비교하여 교환 * 분산식 정렬(Distribute Sort) : 키 값을 기준으로 여러 개로 분해하고 부분집합을 정렬하여 전체 정렬 [정렬 장소에 따른 분류] * 내부 정렬 : 정렬할 자료를 메인 메모리에 올려 정렬하는 방식, 정렬 속도는 빠르나 자료의 양이 메모리에 따라 제한된다. - 교환 .. 2018. 4. 10. [자료구조] Array 와 ArrayList [자료구조] Array 와 ArrayList Array - 논리적 저장 순서와 물리적 저장 순서가 일치 - 인덱스 값을 알고 있다면 Big-O(1)에 해당 원소로 접근 가능 - random access(비순차적 접근)가 가능 [단점] - 삭제 시, 연속적 특징이 깨진다. - 삭제한 원소보다 큰 인덱스 갖는 원소들을 shift 해줘야 하는 비용 발생 = 시간복잡도 O(n) - Array 자료구조의 삭제 기능에 대한 time complexity --> worst case : O(n) - 삽입 시에도 첫번째에 원소를 추가하고 싶다면 1씩 shift해줘야 한다. --> O(n) Linked list - 위의 단점을 해결하기 위한 대안책 - 자기 자신 다음에 올 원소만 기억 - 이 부분만 바꿔주면 삽입과 삭제를 .. 2018. 4. 10. 이전 1 2 3 다음
