Data Structure, O(N) Sorting
02 Mar 2020 | Data Structure개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)
O(N) Sorting
- Not comparison-based approach
- The best performance of the comparison based approach is O(NlogN)
- Therefore, should not be based upon comparisons
- Rather based upon counting and numeric properties
- Variants
- Radix Sort
- Count Sort
- Pros and Cons?
- 단점: 가정이 맞아야하며 comparison-based가 아니어야함
- 장점: 가장 좋은 시간 복잡도
Counting Sorting

- Assumption
- The sequence contains integers(자연수) ranging from 0 to K
- Count the occurrence and produce a sequence based upon the counts
- 시간 복잡도
- O(N+R)
- R = the range of the sequence values
- N = the size of the sequence
def counting_sort(seq):
# prepareing the couting space
max = -9999
min = 9999
for i in range(len(seq)):
if seq[i] > max:
max = seq[i]
if seq[i] < min:
min = seq[i]
counting = list(range(max-min+1))
for i in range(len(counting)):
counting[i] = 0
# perform couting
for i in range(len(seq)):
value = seq[i]
counting[value-min] = counting[value-min] + 1
cnt = 0
for i in range(max-min+1):
for j in range(counting[i]):
seq[cnt] = i + min
cnt += 1
return seq
Radix Sort

- Assumption
- The sequence contains integers
- Sort from the least important digit to the most important digit
- Sort from the least important digit to the most important digit
- Sort from 1000 2 to 1 0002
- 시간복잡도
- O(ND)
- D = the digit number of the largest value
- N = the size of the sequence
- Is this a good approach?
import math
def radix_sort(seq):
# finding the digit number
max = - 99999
for i in range(len(seq)):
if seq[i] > max:
max = seq[i]
d = int(math.log10(max))
print(d)
for i in range(0, d+1):
# palcing values into bucket
buckets = []
for j in range(0, 10):
buckets.append([])
for j in range(len(seq)):
digit = int(seq[j] / math.pow(10, i)) % 10
buckets[digit].append(seq[j])
print(buckets)
# printing the partially sorted values
cnt = 0
for j in range(0, 10):
for k in range(len(buckets[j])):
seq[cnt] = buckets[j][k]
cnt = cnt +1
return seq
Performance of sorting algorithms

- In the real world
- Many people do not concern the time complexity of the sorting
- Why?
- Most of time, people rely on the database and “DESC” and “ASC”
- Most of time, people do not give too much thought on this issue
- Not a good idea
- You need to consider the cost of your system
- Development
- Mainten