Getting started with C# LanguageVerbatim StringsOperatorsExtension MethodsCollection InitializersString InterpolationC# 6.0 FeaturesConstructors and FinalizersKeywordsGenericsReflectionInheritanceNull-Coalescing OperatorUsing StatementString Escape SequencesException HandlingNull-conditional OperatorsBuilt-in TypesLambda expressionsAsync-AwaitPropertiesThreadingUsing DirectiveMethodsYield KeywordEventsLINQ QueriesCommon String OperationsExpression TreesOverload ResolutionString.Formatnameof OperatorUnsafe Code in .NETInitializing PropertiesBindingList<T>ILGeneratorObject initializersXML Documentation CommentsPreprocessor directivesDynamic typeAnonymous typesStructsTuplesEnumAccess ModifiersTask Parallel LibraryAttributesGuidSingleton ImplementationDelegatesNullable typesGarbage Collector in .NetNetworkingArraysEquality OperatorLock StatementAction FiltersXmlDocument and the System.Xml namespaceDateTime MethodsBackgroundWorkerPolymorphismStatic ClassesIndexerIDisposable interfaceAliases of built-in typesImmutabilityXDocument and the System.Xml.Linq namespaceC# 7.0 FeaturesPerforming HTTP requestsGenerating Random Numbers in C#LoopingNamed ArgumentsDiagnosticsInterfacesIEnumerableNaming ConventionsAn overview of c# collectionsChecked and UncheckedRecursionFunctional ProgrammingLiteralsCastingNullReferenceExceptionFunc delegatesLINQ to XMLHash FunctionsHandling FormatException when converting string to other typesCryptography (System.Security.Cryptography)INotifyPropertyChanged interfaceValue type vs Reference typeC# 4.0 FeaturesIQueryable interfaceTask Parallel Library (TPL) Dataflow ConstructsStreamRuntime CompileConditional StatementsInteroperabilityOverflowEquals and GetHashCodeType ConversionParallel LINQ (PLINQ)String ManipulationString ConcatenatePartial class and methodsStopwatchesRegex ParsingC# ScriptC# 3.0 FeaturesAsync/await, Backgroundworker, Task and Thread ExamplesTimersFunction with multiple return valuesBinary SerializationMaking a variable thread safeIComparableCode ContractsIteratorsAssemblyInfo.cs ExamplesFile and Stream I/OCode Contracts and AssertionsCachingC# 5.0 FeaturesImplementing Flyweight Design PatternStringBuilderImplementing Decorator Design PatternAccessing DatabasesT4 Code GenerationMicrosoft.Exchange.WebServices.NET Compiler Platform (Roslyn)Data AnnotationUsing SQLite in C#System.Management.AutomationFileSystemWatcherSystem.DirectoryServices.Protocols.LdapConnectionNamed and Optional ArgumentsComments and regionsC# Authentication handlerPointers & Unsafe CodePointersHow to use C# Structs to create a Union type (Similar to C Unions)BigIntegerDependency InjectionReactive Extensions (Rx)Creational Design PatternsCreating a Console Application using a Plain-Text Editor and the C# Compiler (csc.exe)Reading and writing .zip filesGeneric Lambda Query BuilderImport Google ContactsLambda ExpressionsCLSCompliantAttributeObservableCollection<T>Synchronization Context in Async-AwaitICloneableRead & Understand StacktracesLinq to ObjectsASP.NET IdentityAccess network shared folder with username and passwordAsynchronous SocketStructural Design PatternsO(n) Algorithm for circular rotation of an arrayCreating Own MessageBox in Windows Form ApplicationIncluding Font ResourcesObject Oriented Programming In C#Using json.netGetting Started: Json with C#Windows Communication Foundation

O(n) Algorithm for circular rotation of an array

Other topics

Example of a generic method that rotates an array by a given shift

I would like to point out that we rotate left when the shifting value is negative and we rotate right when the value is positive.

    public static void Main()
    {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int shiftCount = 1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]

        array = new []{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = 15;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -35;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]
    }

    private static void Rotate<T>(ref T[] array, int shiftCount)
    {
        T[] backupArray= new T[array.Length];

        for (int index = 0; index < array.Length; index++)
        {
            backupArray[(index + array.Length + shiftCount % array.Length) % array.Length] = array[index];
        }

        array = backupArray;
    }

The thing that is important in this code is the formula with which we find the new index value after the rotation.

(index + array.Length + shiftCount % array.Length) % array.Length

Here is a little more information about it:

(shiftCount % array.Length) -> we normalize the shifting value to be in the length of the array (since in an array with length 10, shifting 1 or 11 is the same thing, the same goes for -1 and -11).

array.Length + (shiftCount % array.Length) -> this is done due to left rotations to make sure we do not go into a negative index, but rotate it to the end of the array. Without it for an array with length 10 for index 0 and a rotation -1 we would go into a negative number (-1) and not get the real rotation index value, which is 9. (10 + (-1 % 10) = 9)

index + array.Length + (shiftCount % array.Length) -> not much to say here as we apply the rotation to the index to get the new index. (0 + 10 + (-1 % 10) = 9)

index + array.Length + (shiftCount % array.Length) % array.Length -> the second normalization is making sure that the new index value does not go outside of the array, but rotates the value in the beginning of the array. It is for right rotations, since in an array with length 10 without it for index 9 and a rotation 1 we would go into index 10, which is outside of the array, and not get the real rotation index value is 0. ((9 + 10 + (1 % 10)) % 10 = 0)

Contributors

Topic Id: 9770

Example Ids: 30098

This site is not affiliated with any of the contributors.