מבוא לחישוב

שיעור 5 – מיונים וחיפוש בינארי

​

​

מהו מיון

​

• מיון הוא סידור איברי קבוצה מסוימת בסדר עולה או בסדר יורד

​

• הקבוצה היחידה שאנו מכירים עד כה היא מערך, לכן נראה כיצד ממיינים מערך

​

מערך לא ממוין:

מערך ממוין:

© Keren Kalif

מוטיבציה למיון – שיקולי יעילות בחיפוש ערך מסוים

• כדי למצוא את האיבר המינימאלי/המקסימלי במערך, צריך לסרוק את כל האיברים.

​

• אבל, אם המערך ממוין צריך לבדוק מהו ערכו של האיבר הראשון/האחרון בלבד.

​

• כדי למצוא איבר כלשהו, צריך לסרוק את כל האיברים.

​

• אבל, אם המערך ממוין אפשר להשתמש בחיפוש בינארי, שיעיל הרבה יותר.

​

מיון בועות – bubble sort

• הרעיון מאחורי מיון בועות (עבור מיון מהערך הקטן לגדול):
• נבצע השוואה של אלמנטים סמוכים, ונחליף ביניהם אם הם מסודרים לא נכון.
• כדי שנוודא שאנחנו מגיעים בסוף למערך ממוין, נבצע זאת n-1 פעמים (כאשר n הוא מספר איברי המערך).

​

• מה נקבל למעשה?
• באיטרציה הראשונה מובטח לנו שפעפענו ע"י החלפות את האיבר המקסימלי לסוף המערך והוא ממוקם בתא ה- n-1
• באיטרציה השניה מובטח לנו שפעפענו ע"י החלפות את האיבר המקסימלי מבין האיברים 0 עד n-2 ומיקמנו אותו בתא ה- n-2
• וכו' עד סוף המערך

​

• המצב בסיום האיטרציה ה- k שיש לנו את k האיברים הגדולים ביותר במערך ממוינים ב- k התאים האחרונים.

© Keren Kalif

מיון בועות – דוגמת הרצה

אם האיבר השמאלי גדול מהימני, נחליף בינהם

1 < 3 ?

החלף

9 < 3 ?

2 < 9 ?

החלף

המצב כעת הוא שהאיבר המקסימלי אכן נמצא בסוף, ונתייחס רק למערך שמשמאל לקו

3 < 1 ?

2 < 3 ?

החלף

המצב כעת הוא ששני האיברים המקסימאלים אכן נמצאים ממוינים בסוף, ונתייחס רק למערך שמשמאל לקו

2 < 1 ?

© Keren Kalif

מיון בועות - הקוד

public static void main(String[] args) {

int arr[] = {3,8,1,4};

​

for ( ; ; ) {

for ( ; ; ) {

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

​

for (i=0 ; i < arr.length ; i++)

System.out.println(arr[i] + “ “);

System.out.println();

}

int i=arr.length-1

i > 0

i--

int j=0

j < i

j++

© Keren Kalif

מיון בועות – �קצת סדר ופונקציות (1)

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

​

public static void main(String[] args) {()

{

int arr[] = {3,8,1,4};

​

for (int i=arr.length-1 ; i > 0 ; i-- ) {

for (int j=0 ; j < i ; j++ ) {

if (arr[j] > arr[j+1])

swap(arr, j, j+1);

}

}

for (i=0 ; i < size ; i++)

System.out.print(arr[i] + “ “);

System.out.println();

}

© Keren Kalif

מיון בועות – קצת סדר ופונקציות (2)

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

​

public static void sortAscending(int arr[]) {

for (int i=arr.length-1 ; i > 0 ; i-- ) {

for (int j=0 ; j < i ; j++ ) {

if (arr[j] > arr[j+1])

swap(arr, j, j+1);

}

}

}

​

public static void main(String[] args) {

int arr[] = {3,8,1,4};

sortAscending(arr);

for (int i=0 ; i < arr.length ; i++)

System.out.print(arr[i] + “ “);

System.out.println();

}

​

​

© Keren Kalif

מיון בועות – מערך ממוין בסדר יורד

כדי למיין את המערך בסדר יורד,

נרצה לפעפע את האיבר הקטן ביותר לסוף.

לכן השינוי היחידי הוא בתנאי לפני ההחלפה

(וכמובן ששם הפונקציה)

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

​

public static void sortDescending(int arr[]) {

for (int i=arr.length-1 ; i > 0 ; i-- ) {

for (int j=0 ; j < i ; j++ ) {

if (arr[j] < arr[j+1])

swap(arr, j, j+1);

}

}

}

​

public static void main(String[] args) {

int arr[] = {3,8,1,4};

sortDescending(arr);

for (int i=0 ; i < arr.length ; i++)

System.out.print(arr[i] + “ “);

System.out.println();

}

© Keren Kalif

מיון בועות: אופטימיזציה

public static void sortAscending(int arr[]) {

boolean hasChanged=true;

​

for (int i=arr.length-1 ; i > 0 && hasChanged ; i-- ) }

hasChanged = false;

for (int j=0 ; j < i ; j++ ) {

if (arr[j] > arr[j+1]) {

swap(arr, j, j+1);

hasChanged = true;

{

{

{

{

התוספת: לאחר איטרציה ללא כל החלפה, ברור כי המערך כבר ממוין ולכן נפסיק

© Keren Kalif

מיון בועות - ניתוח

• האם זהו מיון טוב (ז"א מהיר)?
• המדד המקובל הוא כמות ההשוואות.
• כאשר המערך גדול, זמני הריצה לא טובים

​

• מה קורה אם כל המערך ממוין כבר?

​

• האם המיון stable?

​

• מה קורה אם חלק מהמערך ממוין?

​

• האם אנחנו חוסכים במספר הכתיבות?

Selection Sort

• במיון זה מחפשים באיטרציה הראשונה את הערך המינימלי ושמים אותו באינדקס ה- 0, ובמקומו שמים את הערך שהיה באינדקס ה- 0
• באיטרציה השניה מחפשים את הערך הנמוך ביותר החל מאינדקס 1, ומחליפים אותו עם הערך באינדקס 1
• וכו'

min

min

min

© Keren Kalif

Selection Sort - הקוד

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

​

public static void selectionSort(int[] arr) {

for (int i=0 ; i < arr.length ; i++) {

int minIndex = i;

for (int j=i+1 ; j < arr.length ; j++) {

if (arr[j] < arr[minIndex])

minIndex = j;

}

swap(arr, i, minIndex);

}

}

​

public static void main(String[] args) {

int[] arr = {5,2,8,1,3};

selectionSort(arr);

}

© Keren Kalif

Selection Sort - פונקציות

public static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

​

public static void selectionSort(int[] arr) {

int minIndex;

for (int i=0 ; i < arr.length ; i++) {

minIndex = findMinIndex(arr,i);

swap(arr, i, minIndex);

}

public static int findMinIndex(int[] arr, int start) {

int minIndex = start;

for (int j=start+1 ; j < arr.length ; j++) {

if (arr[j] < arr[minIndex])

minIndex = j;

}

return minIndex;

}

מיון בחירה - ניתוח

• האם זהו מיון מהיר?
• בד"כ יותר מהיר ממיון בועות. למה?
• אבל עדיין כאשר המערך גדול, זמני הריצה לא טובים

​

• מה קורה אם כל המערך ממוין כבר?

​

• האם המיון stable?

​

• מה קורה אם חלק מהמערך ממוין?

​

• האם אנחנו חוסכים במספר הכתיבות?

Insertion Sort

• הרעיון: נכניס כל איבר למקומו

© Keren Kalif

Insertion Sort - הקוד

public static void insertionSort(int[] arr) {

for (int i=1 ; i < arr.length ; i++) {

for (int j=i ; j > 0 && arr[j-1] > arr[j] ; j--) {

int temp = arr[j];

arr[j] = arr[j-1];

arr[j-1] = temp;

}

}

}

​

public static void main(String[] args) {

int[] arr = {7,1,8,2,3,6,4,5};

insertionSort(arr);

}

http://www.youtube.com/watch?v=ROalU379l3U

© Keren Kalif

מיון הכנסה - ניתוח

• האם זהו מיון מהיר?
• בד"כ יותר מהיר ממיון בחירה. למה?
• אבל עדיין כאשר המערך גדול, זמני הריצה לא טובים

​

• מה קורה אם כל המערך ממוין כבר?

​

• האם המיון stable?

​

• מה קורה אם חלק מהמערך ממוין?

​

• האם אנחנו חוסכים במספר הכתיבות?

השוואת זמני ריצה

• התוכנית Sort.java
• למעשה, המיון של Java משתמש ב- insertion sort כאשר גודל המערך קטן.

מיזוג מערכים ממוינים

מיזוג מערכים ממוינים

• כל עוד יש איברים בשני המערכים:
• נבדוק האם האיבר הנוכחי במערך הראשון קטן/שווה מהאיבר הנוכחי במערך השני:
• אם כן, נעתיק איבר נוכחי מהמערך הראשון לנוכחי בשלישי ונקדם את מיקום האיבר הנוכחי
• אחרת, נעתיק איבר נוכחי מהמערך השני לנוכחי בשלישי ונקדם את מיקום האיבר הנוכחי
• נעתיק את כל מה שנותר מהמערך הראשון לשלישי
• נעתיק את כל מה שנותר מהמערך השני לשלישי

​

רק אחד מהם יקרה...

© Keren Kalif

מיזוג מערכים ממוינים - הקוד

public static int[] mergeArrays(int arr1[], int arr2[]) {

int[] res = new int[arr1.length + arr2.length];

int i=0, j=0;

while ( i < arr1.length && j < arr2.length ) {

if (arr1[i] <= arr2[j])

res[i+j] = arr1[i++];

else

res[i+j] = arr2[j++];

{

​

while ( i < arr1.length) // copy rest of arr1

res[i+j] = arr1[i++];

​

while ( j < arr2.length) // copy rest of arr2

res[i+j] = arr2[j++];

​

return res;

{

i = 0

j = 0

i = 1

j = 1

i = 2

j = 2

j = 3

arr1:

arr2:

res:

© Keren Kalif

חיפוש בינארי

• איך מתמטיקאי מוצא אריה במדבר?

​

• מטרתו של חיפוש בינארי היא למצוא את מיקומו של איבר במערך ממוין

​

• לא ניתן להפעיל חיפוש בינארי על מערך לא ממוין!

חיפוש בינארי - הרעיון

• כל עוד יש במערך איברים:
• נבדוק האם האיבר שאנחנו מחפשים הוא האמצעי
• אם כן, נחזיר את האינדקס שלו
• אחרת אם הוא קטן מהאיבר האמצעי, נחפש אותו בחצי המערך השמאלי
• אחרת, נחפש אותו בחצי המערך הימני
• נחזיר 1- (לא מצאנו..)
• דוגמא, נחפש את הערך 39 במערך:

​

© Keren Kalif

חיפוש בינארי – מימוש רקורסיבי

public static int binarySearch(int[] arr, int item, int left, int right) {

if(left>right)

return -1;

int middle = (left+right)/2;

if(arr[middle]==item)

return middle;

if(arr[middle]>item)

return binarySearch(arr,item,left,middle-1);

else

return binarySearch(arr,item,middle+1,right);

}

מימוש איטרטיבי

public static int binarySearch(int a[], int val) {

int low=0,high=a.length-1, middle;

while (low <= high) {

middle = (low + high)/2;

if (val == a[middle])

return middle;

else if (val < a[middle])

high = middle -1;

else

low = middle +1;

}

return -1;

}

​

​

​

​

​

​

​

public static void main(String[] args) {

int arr[] = {1, 4, 7, 9, 12, 16}, index, value;

value = MyConsole.readInt ("Please enter the value to search: ");

index =

if (index == -1)

System.out.printf("The value %d doesn't exist in the array\n", value);

else

System.out.printf("The value %d exists in index %d\n", value, index);

}

הזיכרון של ה- main

הזיכרון של binarySearch

binarySearch(arr, value);

© Keren Kalif

מימוש איטרטיבי

int binarySearch(int a[], int val) {

int low=0,high=a.length-1, middle;

while (low <= high) {

middle = (low + high)/2;

if (val == a[middle])

return middle;

else if (val < a[middle])

high = middle -1;

else

low = middle +1;

}

return -1;

}

​

​

​

​

public static void main(String[] args) {

int arr[] = {1, 4, 7, 9, 12, 16}, index, value;

value = MyConsole.readInt("Please enter the value to search: ")

index =

if (index == -1)

System.out.printf("The value %d doesn't exist in the array\n", value);

else

System.out.printf("The value %d exists in index %d\n", value, index);

}

הזיכרון של ה- main

binarySearch(arr, value);

הזיכרון של binarySearch

© Keren Kalif

האם אפשר למיין בלי השוואות?

• נניח שיש לנו מערך שמכיל מספרים שלמים, וידוע לנו שטווח כל המספרים הוא בין 0 ל- 100, עם חזרות.

​

• איך אפשר למיין את המערך בלי לבצע השוואות?

Counting sort

public static void countingSort(int[]arr, int N) {

int index;

N++;

int freq[] = new int[N];

for (int i = 0; i < arr.length; i++)

{

index = arr[i];

freq[index]++;

}

int j = 0;

for (int k=0; k<freq.length; k++)

for (int i=0; i<freq[k]; i++)

arr[j++] = k;

}

Improved counting sort

public static void countingSortV2(int[] arr) {

int min = arr[0], max = arr[0];

for (int i = 1; i < arr.length; i++)

{

if (arr[i]>max)

max = arr[i];

else if (arr[i]<min)

min = arr[i];

}

int freq[] = new int[max-min+1];

for (int i = 0; i < arr.length; i++)

freq[arr[i]-min]++;

int j = 0;

for (int k=0; k<freq.length; k++)

for (int i=0; i<freq[k]; i++)

arr[j++] = k+min;

}

כמה נושאים נוספים

• מיון מהיר: QuickSort (קוד דוגמא זמין ב github).
• שימוש בסיפרייה java.util.Arrays
• שימוש ב ArrayList, ArrayList<Type>

​

• שבוע הבא מתחילים לדבר על תכנות מונחה עצמים, למי שיש ניסיון - יכול להסתכן על דגומאות כמו, Point2D

31