{"id":454,"date":"2019-06-05T04:17:24","date_gmt":"2019-06-05T04:17:24","guid":{"rendered":"http:\/\/sites.rutgers.edu\/demetrios-lambropoulos\/?page_id=454"},"modified":"2019-06-10T07:40:55","modified_gmt":"2019-06-10T07:40:55","slug":"lab-3","status":"publish","type":"page","link":"https:\/\/sites.rutgers.edu\/demetrios-lambropoulos\/program-methodology-i-lab-summer-2019\/lab-3\/","title":{"rendered":"Lab 3 – Searching and Sorting"},"content":{"rendered":"

Part 1 – Sorting<\/h1>\n
\n

<\/h2>\n

1.1 – Bubble Sort<\/h2>\n
\n

<\/h3>\n

1.1.1 – Pseudocode<\/h3>\n
\n
\n
swapped =<\/span> 1<\/span>\r\n    while<\/span> swapped\r\n        swapped =<\/span> 0<\/span>\r\n        for<\/span> i from 0<\/span> to size -<\/span> 1<\/span>\r\n           if<\/span> arr[i ><\/span> arr[i +<\/span> 1<\/span>]\r\n              swap( a[i], a[i +<\/span> 1<\/span>] )\r\n              swapped =<\/span> 1<\/span>\r\n<\/pre>\n<\/div>\n
\n
<\/h3>\n
1.1.2 – Time Complexity<\/h3>\n
\n
Bubble sort being the least efficient sorting algorithm covered in this lab has a worst case of O(n^2).<\/p>\n
 <\/p>\n
1.2 – Selection Sort<\/h2>\n
\n
1.2.1 – Pseudocode<\/h3>\n
\n
\n
for<\/span> (i =<\/span> size-<\/span>1<\/span>; i ><\/span> 0<\/span>; --<\/span>i)\r\n{\r\n     Set integer index to 0<\/span> as the index of the largest element\r\n\r\n     Set integer largest to arr[index]\r\n\r\n     for<\/span> (j =<\/span> 1<\/span>; j <=<\/span> i; j++<\/span>)\r\n     {\r\n           if<\/span> (arr[j] ><\/span> largest)\r\n               Change largest to arr[j] and index to j\r\n     }\r\n\r\n     swap(arr[i], arr[index])\r\n}\r\n<\/pre>\n<\/div>\n
 <\/p>\n
\n
1.2.2 – Time Complexity<\/h3>\n
\n
Selection sort is also a quadratic algorithm with a worst case of O(n^2).<\/p>\n
\n
<\/h2>\n
1.3 – Insertion Sort<\/h2>\n
\n
<\/h3>\n
1.3.1 – Pseudocode<\/h3>\n
\n
\n
Set int<\/span> value i to first+<\/span>1<\/span>, where first is the first index of your array\r\n\r\nwhile<\/span> i <<\/span> size\r\n     Set integer tmp to arr[i]\r\n     Set int<\/span> value j to i-<\/span>1<\/span>\r\n\r\n     while<\/span> j >=<\/span> 0<\/span> and arr[j] ><\/span> tmp\r\n           Set arr[j+<\/span>1<\/span>] equal to arr[j]\r\n           Decrement j\r\n     end while<\/span> \r\n\r\n     Set arr[j+<\/span>1<\/span>] equal to tmp\r\n     Increment i\r\nend while<\/span>\r\n<\/pre>\n<\/div>\n
 <\/p>\n
\n
 <\/p>\n
Part 2 – Searching<\/h1>\n
\n
2.1 – Serial Search<\/h2>\n
\n
2.1.1 – Pseudocode<\/h3>\n
\n
\n
\/\/ Searches for a desired element in an array of n elements starting from a[first] <\/span>\r\n\/\/ where first is the\u00a0first index of the array<\/span>\r\n\r\nSet int<\/span> value i to 0<\/span> to use as the index \r\nSet int<\/span> value found to 0<\/span> for<\/span> not found<\/span> (to be used as boolean 0<\/span> -<\/span> not found, 1<\/span> -<\/span> found)\r\n\r\nwhile<\/span> (i <<\/span> n &&<\/span>  not found)\r\n{\r\n      if<\/span> (a[first+<\/span>i] is the desired item)\r\n          set found to 1<\/span>\r\n      else<\/span>\r\n          increment i\r\n}\r\n\r\nif<\/span> (found)\r\n     The desired element was found at a[first+<\/span>i].\r\nelse<\/span>\r\n     The desired element was not found in the array.\r\n<\/pre>\n<\/div>\n
\n
 <\/p>\n
2.1.2 – Time Complexity<\/h3>\n
\n
The average case time complexity for a linear search is (n+1)\/2 array accesses given a linear run time of O(n). A proof for this can be seen as follows:<\/p>\n
Given an array of 5 elements there are five possible cases:<\/p>\n