[go: up one dir, main page]
Scribd
Upload
7 views23 pages

4_sorting

Uploaded by

sandilya23panda
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views23 pages

4_sorting

Uploaded by

sandilya23panda
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 23

Elementary Sorting Algorithms

Sorting – Definitions
 Input: n records, R1 … Rn , from a file.
 Each record Ri has
 a key Ki
 possibly other (satellite) information
 The keys must have an ordering relation  that satisfies
the following properties:
 Trichotomy: For any two keys a and b, exactly one of a  b, a =
b, or a  b is true.
 Transitivity: For any three keys a, b, and c, if a  b and b  c,
then a  c.
The relation = is a total ordering (linear ordering) on keys.
Sorting – Definitions
 Sorting: determine a permutation Π = (p1, … , pn) of n
records that puts the keys in non-decreasing order Kp1 <
… < Kpn.
 Permutation: a one-to-one function from {1, …, n}
onto itself. There are n! distinct permutations of n
items.
 Rank: Given a collection of n keys, the rank of a key is
the number of keys that precede it. That is, rank(Kj) =
|{Ki| Ki < Kj}|. If the keys are distinct, then the rank of a
key gives its position in the output file.
Sorting Terminology
 Internal (the file is stored in main memory and can be randomly
accessed) vs. External (the file is stored in secondary memory &
can be accessed sequentially only)
 Comparison-based sort: uses only the relation among keys, not any
special property of the representation of the keys themselves.
 Stable sort: records with equal keys retain their original relative
order; i.e., i < j & Kpi = Kpj ⇒ pi < pj
 Array-based (consecutive keys are stored in consecutive memory
locations) vs. List-based sort (may be stored in nonconsecutive
locations in a linked manner)
 In-place sort: needs only a constant amount of extra space in
addition to that needed to store keys.
Sorting Categories by operation
 Sorting by Insertion insertion sort, shell sort
 Sorting by Exchange bubble sort, quick sort
 Sorting by Selection selection sort, heap sort
 Sorting by Merging merge sort
 Sorting by Distribution radix sort
Elementary Sorting Methods
 Easier to understand the basic mechanisms of
sorting.
 Good for small files.
 Good for well-structured files that are relatively
easy to sort, such as those almost sorted.
 Can be used to improve efficiency of more
powerful methods.
Bubble Sort
Analysis of Bubble Sort
Analysis of Bubble Sort
 The main advantage of Bubble Sort is the
simplicity of the algorithm.
 In place sorting
 Stable sorting
 The space complexity for Bubble Sort is O(1),
because only a single additional memory space is
required i.e. for temp variable.
 Can be optimized to run in O (n) time in best case
(When the array is already sorted) by stopping the
algorithm if the inner loop didn’t cause any swap.
Example: Insertion Sort
• Idea: like sorting a hand of playing cards
• Start with an empty left hand and the cards facing down
on the table.
• Remove one card at a time from the table, and insert it
into the correct position in the left hand
• compare it with each of the cards already in the hand, from
right to left
• The cards held in the left hand are sorted
• these cards were originally the top cards of the pile on the table
Example: Insertion Sort

To insert 12, we need to make


room for it by moving first 36
and then 24.
Example: Insertion Sort
Example: Insertion Sort
Example: Insertion Sort
Example: Insertion Sort

input array

5 2 4 6 1 3
at each iteration, the array is divided in two sub-arrays:
left sub-array right sub-array

sorted unsorted
Insertion Sort
InsertionSort(A, n)
1. for j = 2 to n do
2. key ← A[j]
3. i←j–1
4. while i > 0 and key < A[i]
5. A[i+1] ← A[i]
6. i←i–1
7. A[i+1] ← key
Example: Insertion Sort
Analysis of Insertion Sort
Analysis of Insertion Sort

Cwc(n) ≤ ∑j = 2 to n (j -1)
= ∑i = 1 to n-1 i
= n(n-1)/2
= Θ(n2)
Selection Sort
Selection-Sort(A, n)
input: array A[1..n] of n unsorted integers
output: same integers in array A now in sorted order

1 for i = 1 to n-1
2 min = i
3 for j = i+1 to n
4 if A[j] < A[min]
5 min = j
6 if min ≠ i then
7 swap A[i] with A[min]
Selection Sort
Selection-Sort(A, n)
input: array A[1..n] of n
unsorted integers
output: same integers in array A
now in sorted order
1 for i = 1 to n-1
2 min = i
3 for j = i+1 to n
4 if A[j] < A[min]
5 min = j
6 if min ≠ i
6 swap (A[i], A[min])
Analysis of Selection sort
 To sort n elements, selection sort performs n-1 passes:
 On 1st pass, it performs n-1 comparisons to find index of
the smallest element
 On 2nd pass, it performs n-2 comparisons …
 On the (n-1)th pass, it performs 1 comparison
 Adding up the comparisons for each pass, we get:
T(n) = 1 + 2 + … + (n - 2) + (n - 1)
Analysis of Selection sort

You might also like