Sorting Algorithm
IT 위키
Sorting Algorithm is an algorithm that arranges elements of a list or array in a specific order, typically numerical or lexicographical. Sorting is a fundamental operation in computer science, used in data processing, searching, and optimization.
Classification of Sorting Algorithms[편집 | 원본 편집]
Sorting algorithms can be classified based on various criteria:
By Complexity[편집 | 원본 편집]
Complexity | Example Algorithms | Description |
---|---|---|
O(n log n) | Merge Sort, Quick Sort, Heap Sort | Efficient sorting algorithms commonly used in practice. |
O(n²) | Bubble Sort, Insertion Sort, Selection Sort | Simple but inefficient for large datasets. |
O(n) | Counting Sort, Radix Sort, Bucket Sort | Used for special cases where elements have constraints. |
By Methodology[편집 | 원본 편집]
- Comparison-Based Sorting: Compares elements to determine their order.
- Examples: Merge Sort, Quick Sort, Heap Sort.
- Non-Comparison Sorting: Uses properties of elements rather than comparisons.
- Examples: Counting Sort, Radix Sort, Bucket Sort.
By Stability[편집 | 원본 편집]
- Stable Sorting: Preserves the relative order of equal elements.
- Examples: Merge Sort, Bubble Sort, Insertion Sort.
- Unstable Sorting: Does not guarantee the order of equal elements.
- Examples: Quick Sort, Heap Sort, Selection Sort.
Common Sorting Algorithms[편집 | 원본 편집]
Bubble Sort[편집 | 원본 편집]
- Process: Repeatedly swaps adjacent elements if they are in the wrong order.
- Time Complexity: O(n²).
- Best Case: O(n) (already sorted list).
- Worst Case: O(n²) (reversed list).
- Stable: Yes.
Selection Sort[편집 | 원본 편집]
- Process: Selects the smallest element and swaps it with the first unsorted element.
- Time Complexity: O(n²).
- Stable: No.
Insertion Sort[편집 | 원본 편집]
- Process: Inserts each element into its correct position in the sorted section.
- Time Complexity: O(n²) (worst case), O(n) (best case).
- Stable: Yes.
Merge Sort[편집 | 원본 편집]
- Process: Recursively divides the array into halves, sorts them, and merges them.
- Time Complexity: O(n log n).
- Stable: Yes.
- Use Case: Efficient for large datasets.
Quick Sort[편집 | 원본 편집]
- Process: Selects a pivot, partitions the array, and recursively sorts the partitions.
- Time Complexity: O(n log n) (average case), O(n²) (worst case).
- Stable: No.
- Use Case: Commonly used in practice due to average-case efficiency.
Heap Sort[편집 | 원본 편집]
- Process: Converts the array into a heap, then extracts the smallest/largest elements.
- Time Complexity: O(n log n).
- Stable: No.
Counting Sort[편집 | 원본 편집]
- Process: Counts the occurrences of elements and places them in order.
- Time Complexity: O(n).
- Stable: Yes.
- Use Case: Works only for integer values within a known range.
Radix Sort[편집 | 원본 편집]
- Process: Sorts numbers by processing digits from least significant to most significant.
- Time Complexity: O(nk), where k is the number of digits.
- Stable: Yes.
Comparison of Sorting Algorithms[편집 | 원본 편집]
Algorithm | Best Case | Worst Case | Average Case | Stable | In-Place |
---|---|---|---|---|---|
Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
Selection Sort | O(n²) | O(n²) | O(n²) | No | Yes |
Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes | No |
Quick Sort | O(n log n) | O(n²) | O(n log n) | No | Yes |
Heap Sort | O(n log n) | O(n log n) | O(n log n) | No | Yes |
Counting Sort | O(n) | O(n + k) | O(n + k) | Yes | No |
Radix Sort | O(nk) | O(nk) | O(nk) | Yes | No |
Applications[편집 | 원본 편집]
Sorting is widely used in:
- Searching Algorithms: Binary search requires sorted data.
- Databases: Query optimization and indexing.
- Computer Graphics: Sorting polygons for rendering.
- Data Science: Preprocessing data for analysis and visualization.