SORTING

• Placing the elements of a list in a certain

order

• “<“, “>” (comparison) and “=“

(assignment) are the only operations
allowed on the input data : comparison-
based sorting

1
 Criteria for Evaluating Sorts
Sorting algorithms can be compared based on several factors.

• Run-time: The number of operations performed (usually swap

and compare).
• Memory: The amount of memory needed beyond what is
needed to store the data to be sorted.
– Some algorithms sort “in place” and use no (or a constant amount of)
extra memory.
– Others use a linear amount, and some an exponential amount.
– Clearly less memory is preferred, although space/time trade-offs are
possible.
• Stability: An algorithm is stable if it preserves the relative order
of equal keys.

2
 QUICKSORT
• Most well-known (good) sorting algorithms are recursive.
They follow the following general strategy:

Given a list of records L

If L has zero or one element, then it is already sorted
Otherwise,
1. Divide in L into two smaller sequences, L1 and L2
2. Recursively sort L1 and L2.
3. Combine L1 and L2 to produce sorted L.

• Mergesort and Quicksort use this technique.

3
 QUICKSORT
• As the name implies quicksort is the fastest known
sorting algorithm in practice.

• Average running time is O(NlogN).

• Fast, due to a very tight and highly optimized inner

loop.

• O(N2) worst-case performance, but this can be made

exponentially unlikely with a little effort.

4
 QUICKSORT: Implementation I
/* Return median of Left, Center, and Right */
/* Order these and hide the pivot */

ElementType Median3( ElementType A[ ], int Left, int

Right )
{
int Center = ( Left + Right ) / 2;

if( A[ Left ] > A[ Center ] )

Swap( &A[ Left ], &A[ Center ] );
if( A[ Left ] > A[ Right ] )
Swap( &A[ Left ], &A[ Right ] );
if( A[ Center ] > A[ Right ] )
Swap( &A[ Center ], &A[ Right ] );

/* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */

Swap( &A[ Center ], &A[ Right - 1 ] ); /* Hide pivot */

return A[ Right - 1 ]; /* Return pivot */
}
5
 QUICKSORT: Implementation II
#define Cutoff ( 10 )
void Qsort( ElementType A[ ], int Left, int Right )
{ int i, j;
ElementType Pivot;

if( Left + Cutoff <= Right )

{ Pivot = Median3( A, Left, Right );
i = Left; j = Right - 1;
for( ; ; )
{ while( A[ ++i ] < Pivot ){ }
while( A[ --j ] > Pivot ){ }
if( i < j )
Swap( &A[ i ], &A[ j ] );
else
break;
}
Swap( &A[ i ], &A[ Right - 1 ] ); /* Restore pivot */

Qsort( A, Left, i - 1 );
Qsort( A, i + 1, Right );
}
else /* Do an insertion sort on the subarray */
InsertionSort( A + Left, Right - Left + 1 );
}
6
 INDIRECT SORTING
• Sometimes, we need to sort large structures or objects by a
certain key.
– payroll records, with each record consisting of a name, address, phone
number, financial information such as salary, and tax information.
– sort this information by one particular field, such as the name or
employee number.

• The fundamental operation in comparison sorts is the swap

swapping two structures can be a very expensive operation,

• A practical solution is to have the input array contain pointers

to the structures. Sort by comparing the keys the pointers
point to, swapping only pointers when necessary.

7
INDIRECT SORTING

8
 INDIRECT SORTING
1. Create an array of pointers (p)

2. Initially p[i] must point to the object stored in a[i]

3. Rearrange the pointers to sort the array (Don’t move objects

in memory at all, change the addresses in the pointers)

4. Rearrange the array (logical re arrangements)

– Rearrange the array in place (in situ permutation )
– no additional space required.

9
Pointer Class definition for Indirect Sorting

11
We can write
int *P[size];
int ** P= new int * [size];

12
Array a 200 100 400 500 300
Addresses A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004
of a
P[0]=1001 P[0]=1000 P[0]=1004 P[0]=1002 P[0]=1003
Sorted p[ ]

13
Array a

Pointer P[0]=1000 P[0]=1001 P[0]=1002 P[0]=1003 P[0]=1004

Array p [ ]
P[0]=1001 P[0]=1000 P[0]=1004 P[0]=1002 P[0]=1003
Sorted p[ ]

14
Pointer Array p [ ] 100 200 300 400 500
P[0]=1001 P[0]=1000 P[0]=1004 P[0]=1002 P[0]=1003
Sorted p[ ] based
on values P[0]=1000 P[0]=1001 P[0]=1002 P[0]=1003 P[0]=1004
we have to
change manually
15
 Initial iteration when i=0

Nextj= 1001-1000  1
A[0]= 100
P[0]= &a[0]  1000
J=1

A[1]= 200
P[1] = &a[j]  1001

200 100 400 500 300

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1001 P[1]=1000 P[2]=1004 P[3]=1002 P[4]=1003

i=0, j=0,
tmp=200
16
 Nextj= 1001-1000  1
A[0]= 100
P[0]= &a[0]  1000
J=1

A[1]= 200
P[1] = &a[j]  1001

100 200 400 500 300

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1000 P[2]=1004 P[3]=1002 P[4]=1003

i=0, J=1
tmp=200
17
 Initial iteration when i=1

P[j] != &a[i] which is false so put temp to

same place and increment i value

100 200 400 500 300

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1004 P[3]=1002 P[4]=1003

i=0, i=1 , j= i
Tmp=200
18
 Initial iteration when i=2

P[j] != &a[i] which is true

Nextj= p[2]- &a[0]  1004 -1000 =4
A[2]= * p[2]  300
P[2]= &a[2]  1002

100 200 400 500 300

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1004 P[3]=1002 P[4]=1003

i=0, i=2 , j= i
Tmp=400
19
 Initial iteration when i=2

Next we need to increment J=nextj J=4

Nextj= p[4]-&a[0]  1003 -1000 =3
A[j] = * p[j]  a[4] = * 1003  500

100 200 300 500

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1002 P[4]=1003

i=0, i=2 ,
Tmp=400 J=4
20
 Initial iteration when i=2

J=4
P[4] != &a[2] which is true
Nextj= p[4]- &a[0]  1003 -1000 =3
A[4]= * p[4]  500
P[4] = &a[4]  1004

100 200 300 500

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1002 P[4]=1004

i=0, i=2 , j=4

Tmp=400
21
 Initial iteration when i=2

J=3
P[3] != &a[2] which is false
A[3]= tmp  400
P[3] = &a[3]  1003

100 200 300 500

Array a
A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1003 P[4]=1004

Sorted p[ ]
i=0, i=2 , j=4
Tmp=400
22
 Initial iteration when i=3

J=3
P[3] != &a[2] which is false
A[3]= tmp  400
P[3] = &a[3]  1003

100 200 300 400 500

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1003 P[4]=1004

i=3 , i=3, i=4 , i=4,

tmp=400 tmp=500
23
 Initial iteration when i=4

J=3
P[3] != &a[2] which is false
A[3]= tmp  400
P[3] = &a[3]  1003

100 200 300 400 500

A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1003 P[4]=1004

i=4 , i=4,
tmp=500
24
 Initial iteration when i=2

J=3
P[3] != &a[2] which is false
A[3]= tmp  400
P[3] = &a[3]  1003

100 200 300 400 500

Array a
A[0]=1000 A[1]=1001 A[2]=1002 A[3]=1003 A[4]=1004

P[0]=1000 P[1]=1001 P[2]=1002 P[3]=1003 P[4]=1004

Sorted p[ ]

SORTED ARRAY
25