C Programming Arrays Sorting - IIT Kanpur

C Programming

Arrays

Sorting

Sorting

Bubble Sort

Bubble sort sinks heaviest element to bottom causing the lighter

elements to bubble up.

Bubble step is as follow:

1

2

3

Start from the first element in the array, compare adjacent pair of

elements.

Swap if required to push the lighter of the pair one position up.

Repeat the comparison of next pair until 1st and 2nd element have

been compared.

Sorting is accomplished by repeating bubble operation n times.

R. K. Ghosh (IIT-Kanpur)

C Programming

February 21, 2011

3/5

C Programming

Arrays

Sorting

Sorting

Bubble Step

7

4

4

4

4

4

4

4

7

6

6

6

6

6

6

6

6

7

3

3

3

3

3

3

3

3

7

1

1

1

1

1

1

1

1

7

2

2

2

2

2

2

2

2

7

5

5

5

5

5

5

5

5

7

0

0

0

0

0

0

0

0

7

R. K. Ghosh (IIT-Kanpur)

C Programming

February 21, 2011

3/5

C Programming

Arrays

Sorting

Sorting

Code for Bubble Sort

void bubbleSort ( int a [ ] , int n) {

i n t i , j , temp ;

f o r ( i = n ?1; i > 0 ; i ??) // E x e c u t e b u b b l e o p e r a t i o n n t i m e s

f o r ( j = 1 ; j a [ j ] ) {

temp = a [ j ? 1 ] ;

a [ j ?1] = a [ j ] ;

a [ j ] = temp ;

}

}

R. K. Ghosh (IIT-Kanpur)

C Programming

February 21, 2011

3/5

C Programming

Arrays

Sorting

Sorting

Putting All Together

#i n c l u d e

#i n c l u d e < s t d i o . h>

#d e f i n e N 10

i n t main ( ) {

i n t a [N ] ;

i n t n = s i z e o f ( a )/ s i z e o f ( a [ 0 ] ) ;

generate (a , n );

p r i n t f ( ¡± U n s o r t e d i n p u t \n¡± ) ;

printArray (a , n );

bubbleSort (a , n ) ;

p r i n t f ( ¡± S o r t e d o u t p u t \n¡± ) ;

printArray (a , n );

}

R. K. Ghosh (IIT-Kanpur)

C Programming

February 21, 2011

3/5

C Programming

Arrays

Sorting

Sorting

Insertion Sort

Based on the act of picking cards and arranging the hand in sorted

order.

Initially, only the first element of the array is in sorted order.

The input element is compared element-wise with sorted part of the

array.

If the input is smaller than the current element of the sorted part,

consider the next element of sorted part.

Else position for the input element is found.

R. K. Ghosh (IIT-Kanpur)

C Programming

February 21, 2011

3/5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download