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

Sorting in C

Uploaded by

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

Sorting in C

Uploaded by

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

Introduction to

Sorting
What is Sorting?

Sorting: an operation that segregates


items into groups according to
specified criterion.

A={3162134590}

A={0112334569}
Why Sort and Examples

Consider:
●
Sorting Books in Library (Dewey system)
●
Sorting Individuals by Height (Feet and Inches)
●
Sorting Movies in Blockbuster (Alphabetical)
●
Sorting Numbers (Sequential)
Types of Sorting Algorithms

There are many, many different types of sorting


algorithms, but the primary ones are:

●
Bubble Sort ●
Quick Sort
●
Selection Sort ●
Radix Sort
●
Insertion Sort ●
Swap Sort
●
Merge Sort
●
Shell Sort
●
Heap Sort
Review of Complexity
Most of the primary sorting algorithms run on
different space and time complexity.

Time Complexity is defined to be the time the


computer takes to run a program (or algorithm in
our case).

Space complexity is defined to be the amount of


memory the computer needs to run a program.
O(n), Ω(n), & Θ(n)

●
An algorithm or function T(n) is O(f(n)) whenever
T(n)'s rate of growth is less than or equal to f(n)'s
rate.
●
An algorithm or function T(n) is Ω(f(n))
whenever T(n)'s rate of growth is greater than or
equal to f(n)'s rate.
●
An algorithm or function T(n) is Θ(f(n)) if and
only if the rate of growth of T(n) is equal to f(n).
Common Big-Oh’s
Time complexity Example
O(1) constant Adding to the front of a linked list
O(log N) log Finding an entry in a sorted array
O(N ) linear Finding an entry in an unsorted array
O(N log N) n-log-n Sorting n items by ‘divide-and-conquer’
O(N 2) quadratic Shortest path between two nodes in a graph
O(N 3) cubic Simultaneous linear equations

Front 1
5 Initial: 1
0
8
(Binary)
(Linear) Final: 63
9
Finding 8: 21
22
50
Big-Oh to Primary Sorts

●
Selection Sort = n²
●
Insertion Sort = n²
●
Merge Sort = n log(n)
●
Quick Sort = n log(n)
Time Efficiency

• How do we improve the time efficiency of a program?

• The 90/10 Rule


90% of the execution time of a program is spent in
executing 10% of the code

• So, how do we locate the critical 10%?


• software metrics tools
• global counters to locate bottlenecks (loop executions,
function calls)
Time Efficiency
Improvements

Possibilities (some better than others!)

• Move code out of loops that does not belong there


(just good programming!)
• Remove any unnecessary I/O operations (I/O operations
are expensive time-wise)
• Code so that the compiled code is more efficient

Moral - Choose the most appropriate algorithm(s) BEFORE


program implementation
Stable sort algorithms

Ann 98 Ann 98
●
A stable sort keeps
equal elements in Bob 90 Joe 98
the same order Dan 75 Bob 90
●
This may matter
when you are sorting Joe 98 Sam 90
data according to
Pat 86 Pat 86
some characteristic
●
Example: sorting Sam 90 Zöe 86
students by test
scores Zöe 86 Dan 75

original stably
array sorted
Unstable sort algorithms

●
An unstable sort Ann 98 Joe 98
may or may not Bob 90 Ann 98
keep equal
Dan 75 Bob 90
elements in the
same order Joe 98 Sam 90
●
Stability is Pat 86 Zöe 86
usually not
Sam 90 Pat 86
important, but
sometimes it is Zöe 86 Dan 75
important
original unstably
array sorted
Selection Sorting
Step:
●
1. select the smallest element
●
among data[i]~ data[data.length-1];
●
2. swap it with data[i]; 20 8 5 10 7
●
3. if not finishing, repeat 1&2
5 8 20 10 7

5 7 20 10 8

5 7 8 10 20

5 7 8 10 20
Insertion Sorting
●
Place ith item in proper position:
– temp = data[i]
– shift those elements data[j] which greater
than temp to right by one position
– place temp in its proper position
Insert Action: i=1
temp
8 20 8 5 10 7 i = 1, first iteration

8 20 20 5 10 7

--- 8 20 5 10 7
Insert Action: i=2
temp
5 8 20 5 10 7 i = 2, second iteration

5 8 20 20 10 7

5 8 8 20 10 7

--- 5 8 20 10 7
Insert Action: i=3
temp
10 5 8 20 10 7 i = 3, third iteration

10 5 8 20 20 7

--- 5 8 10 20 7
Insert Action: i=4

temp
7 5 8 10 20 7 i = 4, forth iteration

7 5 8 10 20 20

7 5 8 10 10 20

7 5 8 8 10 20

--- 5 7 8 10 20

rio.ecs.umass.edu/ece242/slides/lect-sorting.ppt

You might also like