{"id":34740,"date":"2024-11-01T09:31:28","date_gmt":"2024-11-01T09:31:28","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34740"},"modified":"2024-11-01T11:26:45","modified_gmt":"2024-11-01T11:26:45","slug":"swift-coding-test-course-merge-sort","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34740\/","title":{"rendered":"Swift Coding Test Course, Merge Sort"},"content":{"rendered":"

<\/p>\n

\n

Hello. Today, we will learn about the Merge Sort algorithm implemented in Swift. This tutorial will start from the basics of Merge Sort and explain its application in actual coding tests in detail.<\/p>\n<\/header>\n

\n

What is Merge Sort?<\/h2>\n

Merge Sort is a sorting algorithm based on the divide and conquer strategy. It divides the array into two halves, sorts each sub-array, and then merges the two sorted sub-arrays into one sorted array. Merge Sort has an average and worst-case time complexity of O(n log n) and is a stable sort.<\/p>\n<\/section>\n

\n

Principle of Merge Sort<\/h2>\n

The process of Merge Sort is as follows:<\/p>\n

    \n
  1. Given the original array, it is split into two sub-arrays at the midpoint.<\/li>\n
  2. Merge Sort is recursively performed on each sub-array.<\/li>\n
  3. The two sorted sub-arrays are merged to create one sorted array.<\/li>\n<\/ol>\n

    The important point here is that the sub-arrays are sorted at each step. The entire array is sorted by merging these sorted arrays back together.<\/p>\n<\/section>\n

    \n

    Problem: Sort Integers<\/h2>\n

    Write a function in Swift that sorts a given list of integers in ascending order. An example input is as follows:<\/p>\n

    \n            let nums = [38, 27, 43, 3, 9, 82, 10]\n        <\/code><\/pre>\n
    To solve this problem, you need to apply the principles of Merge Sort explained above.<\/p>\n<\/section>\n
    \n
    Implementing Merge Sort<\/h2>\n
    Now, let’s implement Merge Sort in Swift. Below is the complete code:<\/p>\n
    \n            func mergeSort(_ array: [Int]) -> [Int] {\n                \/\/ 1. If the size of the array is less than 1, return the original array\n                if array.count < 2 {\n                    return array\n                }\n                \n                \/\/ 2. Split the array at the midpoint\n                let midIndex = array.count \/ 2\n                let leftArray = mergeSort(Array(array[0.. [Int] {\n                var mergedArray: [Int] = []\n                var leftIndex = 0\n                var rightIndex = 0\n                \n                \/\/ 4. Merge by comparing the two arrays\n                while leftIndex < left.count && rightIndex < right.count {\n                    if left[leftIndex] < right[rightIndex] {\n                        mergedArray.append(left[leftIndex])\n                        leftIndex += 1\n                    } else {\n                        mergedArray.append(right[rightIndex])\n                        rightIndex += 1\n                    }\n                }\n                \n                \/\/ 5. Add remaining elements\n                while leftIndex < left.count {\n                    mergedArray.append(left[leftIndex])\n                    leftIndex += 1\n                }\n                \n                while rightIndex < right.count {\n                    mergedArray.append(right[rightIndex])\n                    rightIndex += 1\n                }\n                \n                return mergedArray\n            }\n\n            \/\/ Main\n            let nums = [38, 27, 43, 3, 9, 82, 10]\n            let sortedNums = mergeSort(nums)\n            print(sortedNums) \/\/ Result: [3, 9, 10, 27, 38, 43, 82]\n        <\/code><\/pre>\n
    The above code sorts the input list of numbers using Merge Sort and prints the result. Comments are added at each step to aid understanding.<\/p>\n<\/section>\n
    \n
    Code Explanation<\/h2>\n
    Let's take a look at the code line by line:<\/p>\n
      \n
    1. if array.count < 2 { return array }<\/code>: If the size of the array is less than 1, it is already sorted, so it is returned as is.<\/li>\n
    2. let midIndex = array.count \/ 2<\/code>: Calculates the midpoint index of the array.<\/li>\n
    3. let leftArray = mergeSort(Array(array[0..: Recursively sorts the left sub-array.<\/li>\n
    4. let rightArray = mergeSort(Array(array[midIndex..: Recursively sorts the right sub-array.<\/li>\n
    5. return merge(leftArray, rightArray)<\/code>: Merges the sorted left and right arrays and returns the result.<\/li>\n<\/ol>\n
      In the merge function, indices are tracked as the two arrays are compared and merged. If one array is exhausted, the remaining elements are added to produce the final result.<\/p>\n<\/section>\n
      \n
      Advantages and Disadvantages of Merge Sort<\/h2>\n
      Merge Sort has the following advantages and disadvantages:<\/p>\n
      Advantages:<\/h3>\n
        \n
      1. Stable sorting: The relative order of elements with equal values is preserved.<\/li>\n
      2. Time complexity of O(n log n): It provides a relatively fast sorting performance proportional to the amount of data.<\/li>\n
      3. Can be applied to linked lists as well as arrays of fixed size: It can be used in structures that utilize pointers.<\/li>\n<\/ol>\n
        Disadvantages:<\/h3>\n
          \n
        1. Requires additional memory: Because a new array is created during the merging process, the space complexity is O(n).<\/li>\n
        2. In simpler cases (e.g., nearly sorted cases), simpler algorithms like insertion sort may perform better.<\/li>\n<\/ol>\n<\/section>\n
          \n
          Additional Problems for Skill Improvement<\/h2>\n
          Now that you understand Merge Sort, practice further with these additional problems:<\/p>\n
            \n
          1. Write a function that takes an array of integers and returns a sorted array with duplicates removed.<\/li>\n
          2. Implement an algorithm that finds the index of an element with a specific value in a sorted array using binary search.<\/li>\n
          3. Write a function in Swift that merges multiple input arrays into one sorted array.<\/li>\n<\/ol>\n<\/section>\n