Line data    Source code

       1             : /*
       2             :  *
       3             :  *    Copyright (c) 2020-2021 Project CHIP Authors
       4             :  *    Copyright (c) 2013-2017 Nest Labs, Inc.
       5             :  *    All rights reserved.
       6             :  *
       7             :  *    Licensed under the Apache License, Version 2.0 (the "License");
       8             :  *    you may not use this file except in compliance with the License.
       9             :  *    You may obtain a copy of the License at
      10             :  *
      11             :  *        http://www.apache.org/licenses/LICENSE-2.0
      12             :  *
      13             :  *    Unless required by applicable law or agreed to in writing, software
      14             :  *    distributed under the License is distributed on an "AS IS" BASIS,
      15             :  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      16             :  *    See the License for the specific language governing permissions and
      17             :  *    limitations under the License.
      18             :  */
      19             : 
      20             : #pragma once
      21             : 
      22             : #include <algorithm>
      23             : #include <stdint.h>
      24             : #include <stdlib.h>
      25             : 
      26             : namespace chip {
      27             : namespace Sorting {
      28             : 
      29             : /**
      30             :  *
      31             :  * Impements the bubble sort algorithm to sort an array
      32             :  * of items of size 'n'.
      33             :  *
      34             :  * T should be swappable using std::swap (i.e implements Swappable).
      35             :  *
      36             :  * The provided comparison function SHALL have the following signature:
      37             :  *
      38             :  *      bool Compare(const T& a, const T& b);
      39             :  *
      40             :  * If a is deemed less than (i.e is ordered before) b, return true.
      41             :  * Else, return false.
      42             :  *
      43             :  * This is a stable sort.
      44             :  *
      45             :  * NOTE: This has a worst case time complexity of O(n^2). This
      46             :  * is well-suited for small arrays where the time trade-off is
      47             :  * acceptable compared to the lower flash cost for the simple sorting
      48             :  * implementation.
      49             :  *
      50             :  */
      51             : template <typename T, typename CompareFunc>
      52          46 : void BubbleSort(T * items, size_t n, CompareFunc f)
      53             : {
      54         150 :     for (size_t i = 0; i < (n - 1); i++)
      55             :     {
      56         383 :         for (size_t j = 0; j < (n - i - 1); j++)
      57             :         {
      58         279 :             const T & a = items[j + 1];
      59         279 :             const T & b = items[j];
      60             : 
      61         279 :             if (f(a, b))
      62             :             {
      63         125 :                 std::swap(items[j], items[j + 1]);
      64             :             }
      65             :         }
      66             :     }
      67          46 : }
      68             : 
      69             : /**
      70             :  *
      71             :  * Impements the insertion sort algorithm to sort an array
      72             :  * of items of size 'n'.
      73             :  *
      74             :  * The provided comparison function SHALL have the following signature:
      75             :  *
      76             :  *      bool Compare(const T& a, const T& b);
      77             :  *
      78             :  * If a is deemed less than (i.e is ordered before) b, return true.
      79             :  * Else, return false.
      80             :  *
      81             :  * This is a stable sort.
      82             :  *
      83             :  */
      84             : template <typename T, typename CompareFunc>
      85             : void InsertionSort(T * items, size_t n, CompareFunc f)
      86             : {
      87             :     for (size_t i = 1; i < n; i++)
      88             :     {
      89             :         const T key = items[i];
      90             :         int j       = static_cast<int>(i) - 1;
      91             : 
      92             :         while (j >= 0 && f(key, items[j]))
      93             :         {
      94             :             items[j + 1] = items[j];
      95             :             j--;
      96             :         }
      97             :         items[j + 1] = key;
      98             :     }
      99             : }
     100             : 
     101             : } // namespace Sorting
     102             : 
     103             : } // namespace chip