Codogos de ordenamiento

DATA STRUCTURES
UNIT I Asdr´bal L´pez Chau u o
Zumpango, Autonomous University of Mexico State

February 24th , 2011

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

1 / 37

Data Structures

UNIT I Topics
1

SORTING ALGORITHMS Basic sorting algorithms

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

2 / 37

Contents ofthis Section

1

Sorting algorithms The Interchange Sort Algorithm
A brief note on swap

Selection sort algorithm The Insertion Sort Algorithm The Bubble Sort algorithm Activities Recommendations

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

3 / 37

Contents of this Subsection

1

Sorting algorithms The Interchange Sort Algorithm
A brief note on swapSelection sort algorithm The Insertion Sort Algorithm The Bubble Sort algorithm Activities Recommendations

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

2 / 37

The Interchange Sort Algorithm

The Interchange Sort Algorithm is maybe the simplest sorting algorithm. Example: Consider the entry Data=[9,5,7,3]

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

DataStructures

February 2011

3 / 37

The Interchange Sort Algorithm
Example: Original Data=[9,5,7,3] Pass 1. Compare the first element against the rest∗ , ensure that the smallest is in the first position. 9 ↑ Swap! (Why?) 5 ↑ 9 ↑ 7 3 5 ↑ 7 3

*: We will not consider previous elements in next steps

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

4 / 37

TheInterchange Sort Algorithm
Example: Original Data=[9,5,7,3] Pass 1. Continues Compare the first element against the rest, ensure that the smallest is in the first position. 5 ↑ No swap, continue 5 ↑ Swap? 9 7 3 ↑ 9 7 ↑ 3

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

5 / 37

The Interchange Sort Algorithm
Example: Original Data=[9,5,7,3] Pass 1. ContinuesCompare the first element against the rest, ensure that the smallest is in the first position. 5 ↑ Swap?, yes! 3 ↑ End of pass 1 9 7 5 ↑ 9 7 3 ↑

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

6 / 37

The Interchange Sort Algorithm

Example: Original Data=[9,5,7,3] Pass 2. Begins Compare the second element against the rest, ensure that the smallest is in the secondposition. 3 9 ↑ 7 ↑ 5

Swap 3 7 ↑ 9 ↑ 5

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

7 / 37

The Interchange Sort Algorithm
Example: Original Data=[9,5,7,3] Pass 2. Continues Compare the second element against the rest, ensure that the smallest is in the second position. 3 7 ↑ 9 5 ↑

Swap! 3 5 ↑ 9 7 ↑

End of pass 2

Asdr´bal L. Chau (CU-UAEM ZUMPANGO)u

Data Structures

February 2011

8 / 37

The Interchange Sort Algorithm
Example: Original Data=[9,5,7,3] Pass 3. Begins Compare the third element against the rest, ensure that the smallest is in the third position. 3 5 9 ↑ 7 ↑

Swap 3 5 7 ↑ 9 ↑

End of pass 3, and end of algorithm! Sorted [3,5,7,9]
Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u Data Structures February 2011 9 / 37

TheInterchange Sort Algorithm
A BRIEF NOTE ON SWAP. Almost all sorting algorithms need swap operation. Common notations: A B A↔B Swap(A,B) Swap(A[i],A[j]) Pseudo code: Swap(A,B){ tmp ← A A ← B B ← tmp }
Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u Data Structures February 2011 10 / 37

The Interchange Sort Algorithm
Now the algorithm... Data: Data: An array of N elements Result: The array Data sortedfor i = 0 to N − 2 do //From the first to the penultimate number for j = i + 1 to N − 1 do // if Data[i] > Data[j] then //Check if Data [i] is sorted Data[i] Data[j] ; /* Swap */ end end end return Data Algorithm 1: The Interchange Sort Algorithm

1

2 3 4 5 6 7 8

Asdr´bal L. Chau (CU-UAEM ZUMPANGO) u

Data Structures

February 2011

11 / 37

Contents of this Subsection

1...