JavaRush /Java блог /Архив info.javarush /Сортировка вставками
Helga
26 уровень

Сортировка вставками

Статья из группы Архив info.javarush
Ребята! Помогите найти ошибку! Сортировка вставками - 1Задача такая: Написать сортировку массива вставками с использованием бинарного поиска и функции System.arraycopy; Вот код:

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main
        {

    public static void main(String[] args) throws IOException {
        int[] arr = createArray();
        System.out.println(Arrays.toString(arr));
        //int[] arr1 = sortArray(arr);
        int[] arr1 = sortArray1(arr);
        System.out.println(Arrays.toString(arr1));


    }
            // creating array
    public static int[] createArray() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] result = new int[10];
        for (int i = 0; i < result.length; i++)
            result[i] = Integer.parseInt(reader.readLine());
        return result;
    }

            // sorting array (insertions)
    public static int[] sortArray(int[] array) {
          for (int i = 1; i < array.length; i++)
                {
                    int currVal = array[i];
                    int keyPrev = i - 1;
                    while ((keyPrev >= 0)&&(currVal < array[keyPrev]))
                    {
                        array[keyPrev+1] = array[keyPrev];
                        array[keyPrev] = currVal;
                        keyPrev--;
                    }
                }
                return array;
            }

          // sorting array (insertion + binary Search + System.arraycopy)
    public static int[] sortArray1(int[] array) {
        for (int i = 1; i < array.length; i++)
        {
            int currVal = array[i];
            int keyPrev = i - 1;
            int searchResult = Arrays.binarySearch(array, 0, keyPrev, array[i]);
            if ((searchResult >=0))
            {
                System.arraycopy(array, searchResult, array, searchResult+1, keyPrev-searchResult+1);
                array[searchResult]=currVal;
            }
            else
            {
                int sR = Math.abs(searchResult)-1;
                System.arraycopy(array, sR, array, sR+1, keyPrev-sR+1);
                array[sR]=currVal;
            }

        }
        return array;
    }
}
А вот вывод:

[7, 2, 8, 5, 7, 3, 5, 7, 3, 4]
[2, 3, 3, 4, 5, 5, 7, 7, 8, 7]
По логике должна работать, а на деле не сортирует последний элемент!
Комментарии (2)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
GreegAV Уровень 8
9 мая 2017
Когда кто-то зайдет сюда с поиска гугла — пусть у него будет рабочий ответ

import java.util.Arrays;

public static void sort(int[] arr) {
for (int k = 1; k < arr.length; k++) {
int newElement = arr[k];
int index;
index = Arrays.binarySearch(arr, 0, k, newElement);
if (index < 0) {
index = -(index) — 1;
}
System.arraycopy(arr, index, arr, index + 1, k — index);
arr[index] = newElement;
}
}